36th成都區域賽網絡賽 hdoj4039 The Social Network（建圖+字符串處理）
來源：程序員人生 發布時間：2014-09-09 19:22:38 閱讀次數：2157次
這題是某年成都區域賽網絡賽的一題。
這題思路很簡單，但是從時間上考慮，最好還是不要用矩陣存儲，我用的鏈式前向星。
采用線上查詢。利用map對字符串編號，因為很方便。要推薦的朋友，其實就是朋友的朋友（這里指的是直接朋友，圖中即指有直接邊相連的）。
所以在尋找時，只需要查找朋友的朋友，并計數。
注意:在輸出時不能有對于的空格。
附代碼：
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#include<algorithm>
int n,m;
char s11[20],s22[20];
string g[20100],l[20100];
int next[201000],head[2010],key[201000];
int num;
void add(int u,int v)
{
key[num]=v;
next[num]=head[u];
head[u]=num++;
}
int main()
{
int T,pp=0;
scanf("%d",&T);
while (T--)
{
map<string,int> hash;
int n,m,i,j,k;
string s1,s2;
int cnt=0;
num=0;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for (i=0;i<n;++i)
{
scanf("%s%s",s11,s22);
s1=string(s11);
s2=string(s22);
if (hash[s1]==0)
hash[s1]=++cnt,l[cnt]=s1;
if (hash[s2]==0)
hash[s2]=++cnt,l[cnt]=s2;
add(hash[s1],hash[s2]);
add(hash[s2],hash[s1]);
}
printf("Case %d:
",++pp);
for (i=0;i<m;++i)
{
scanf("%s",s11);
s1=string(s11);
int p=hash[s1];
int f[20100],flag[20010];
memset(f,0,sizeof(f));
memset(flag,0,sizeof(flag));
for (k=head[p];k!=-1;k=next[k]) flag[key[k]]=-1;
for (k=head[p];k!=-1;k=next[k])
if (key[k]!=p)
{
for (j=head[key[k]];j!=-1;j=next[j])
if (key[j]!=key[k] && key[j]!=p && flag[key[j]]==0)
{
f[key[j]]++;
}
}
int Max=-1;
for (k=1;k<=cnt;++k)
{
Max=max(Max,f[k]);
// printf("%d
",f[k]);
}
if (Max==0)
{
printf("-
");
continue;
}
int q=0;
for (k=1;k<=cnt;++k)
if (Max==f[k])
{
g[q++]=l[k];
}
sort(g,g+q);
for (k=0;k<q-1;++k) cout << g[k] << " ";
cout << g[q-1];
cout << endl;
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
