hdu 4039 The Social Network

it2022-05-06  6

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

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

最新回复(0)