因为N数据实在是1000*1000。相当的小。 最多开到2000*2000。 这样的话,直接暴力就可以解决了。
然后我们用trie树建立映射关系,之后开始建图搜索匹配。 n*n的搜索完全可以接受。
题目意思就是模拟推荐好友的功能。
/* * @author ipqhjjybj * @time 20130907 */ #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <queue> #define foreach(it,x) for(vector<int>::iterator it=x.begin();it!=x.end();it++) using namespace std; const int N=2111; struct cmp{ char *s; bool operator < (const cmp & tmp) const{ return strcmp(s,tmp.s)>0; }; cmp(){}; cmp(char *_s){ s=_s; } }; struct node{ node *go[26]; int id; int end; void clear(){ memset(go,0,sizeof(go)); id=-1; end=0; } }AlphaTree[4000000],*root,*cnt; int cid; char str[N][40]; int g[N][N]; int n,q; vector<int> vi[N]; void Init(){ root=cnt=AlphaTree; root->clear(); cnt++; cid=0; memset(g,0,sizeof(g)); } int Insert(char *s){ node *cur=root; char *p=s; int x; for( ;*s;s++){ x=*s-'a'; if(!cur->go[x]){ cur->go[x]=cnt; cnt->clear(); cnt++; } cur=cur->go[x]; } if(cur->id==-1){ cur->id=cid; strcpy(str[cid],p); vi[cid].clear(); cid++; } return cur->id; } int ct[N]; void solve(int id){ for(int i=0;i<cid;i++) ct[i]=0; foreach(u,vi[id]) foreach(v,vi[*u]){ if(!g[id][*v]&&*v!=id){ ct[*v]++; } } int max_value=0; for(int i=0;i<cid;i++){ max_value=max(max_value,ct[i]); } if(!max_value){ printf("-\n"); }else{ priority_queue<cmp> Q; for(int i=0;i<cid;i++) if(max_value==ct[i]) Q.push(cmp(str[i])); printf("%s",Q.top().s); Q.pop(); while(!Q.empty()){ printf(" %s",Q.top().s); Q.pop(); } printf("\n"); } } int main(){ int t,tt=0,id1,id2; char str1[20],str2[20]; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&q); Init(); for(int i=0;i<n;i++){ scanf("%s %s",str1,str2); id1=Insert(str1); id2=Insert(str2); if(!g[id1][id2]){ vi[id1].push_back(id2); vi[id2].push_back(id1); } g[id1][id2]=g[id2][id1]=1; } printf("Case %d:\n",++tt); while(q--){ scanf("%s",str1); solve(Insert(str1)); } } return 0; }