36th成都区域赛网络赛 hdoj4039 The Social Network（建图+字符串处理）
来源：程序员人生 发布时间：2014-09-09 19:22:38 阅读次数：2015次
这题是某年成都区域赛网络赛的一题。
这题思路很简单，但是从时间上考虑，最好还是不要用矩阵存储，我用的链式前向星。
采用线上查询。利用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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
