hdu 4039 The Social Network

hdu 4039 The Social Network

题意：给出N对好友关系，之后Q次提问，问可以对该用户推荐的相识度最高的好友；

推荐好友满足的条件：该用户的所有好友的好友中，出现次数最多的，而且推荐好友本身不是该用户的好友；若有多个推荐好友时，按字典序输出；

分析：

嘿嘿，我的做法有点暴力，600+ms；

首先对所有用户的名字（字符串）标号，好处理一些，这里用了字典树实现了；

接下来，用邻接矩阵表示任意俩个用户直接的关系，再者，对与每一次询问，遍历该用户所有好友的好友，找出出现次数最多的；

最后，若有多个推荐好友时，要字典树输出，额，我用优先队列做了，重载操作符，之后直接丢进去，再输出就可以了

View Code #include<iostream>#include<string>#include<queue>using namespace std;int num;short map[2001][2001];struct str{char s[16]; friend bool operator<(const str ne1,const str ne2)//重载操作符 {if(strcmp(ne1.s,ne2.s)==1)return true;return false; }}st[2001];typedef struct node { int cnt; struct node *next[26]; }*tree,Trie; tree root; int ex[2001],f[2001];inline int GetNum(char *t)//用字典树对字符串编号{ tree p = root,newnode;for(int i = 0;i < strlen(t); ++i){int u = t[i] - 'a';if(p->next[u]==NULL) { newnode=(tree)malloc(sizeof(Trie)); newnode->cnt=-1;for(int j=0;j<26;j++) newnode->next[j]=NULL; p->next[u]=newnode; p=newnode; }else p = p->next[u]; }if(p->cnt == -1) //该节点未出现过 p->cnt = num ++;return p->cnt;}int main(){int T=0,cas,n,q,n1,n2;char str1[16],str2[16]; scanf("%d",&cas);while(cas--) { root=(tree)malloc(sizeof(Trie)); root->cnt=-1;for(int j=0;j<26;j++) root->next[j]=NULL; num=0; scanf("%d %d",&n,&q); memset(map,0,sizeof(map));for(int i=0;i<n;i++) { scanf("%s %s",str1,str2); n1=GetNum(str1); n2=GetNum(str2); strcpy(st[n1].s,str1); strcpy(st[n2].s,str2); map[n1][n2]=map[n2][n1]=1; } printf("Case %d:\n",++T);while(q--) {int max=0,count=0; memset(f,0,sizeof(f)); memset(ex,0,sizeof(ex)); scanf("%s",str1); n1=GetNum(str1);for(int i=0;i<num;i++) {if(n1==i)continue;//自己跟自己，肯定…… if(map[n1][i]==1) {for(int j=0;j<num;j++) {if(i==j||j==n1)continue;//推荐好友本身不能是自己的好友 if(!map[n1][j]&&map[i][j]==1) { ex[j]++;if(ex[j]>=max) {if(ex[j]==max)//若有出现次数相同的，累加 f[count++]=j;else { count=0;//若有出现次数更多的，直接覆盖 f[count++]=j; } max=ex[j]; } } } } } priority_queue<str> Q;if(count==0) printf("-");else {for(int i=0;i<count;i++) Q.push(st[f[i]]); }for(int i=0;i<count;i++) {if(i==0) printf("%s",Q.top().s);else printf(" %s",Q.top().s); Q.pop(); } printf("\n"); } }return 0;}

转载于:https://www.cnblogs.com/nanke/archive/2011/09/12/2173990.html

相关资源：数据结构—成绩单生成器