hdu4460 Friend Chains

题目链接

每个点跑一遍 SPFA，然后取 (max)。

code:

#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define Clear(n) memset(n,0,sizeof(n))
map<string,int> t; 
const int M=10010,N=1010;
int ver[M<<1],head[N],nxt[M<<1],tot=0,n,m,f[N],dis[N],ans=-1;
int c[N];
bool book[N];
void add(int x,int y)
{
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
struct node
{
	int ver,step;
	node(int x,int y) {ver=x,step=y;}
};
void init()
{
	Clear(book);
	t.clear();
	Clear(head);
	Clear(ver);
	Clear(nxt);
	tot=0;
	Clear(f);
}
void spfa(int st)
{
	queue<int> que;
    memset(dis,0x3f,sizeof(dis));
    memset(book,0,sizeof(book));
    dis[st]=0;
    book[st]=true;
    c[st]=1;
    que.push(st);
    while(!que.empty())
    {
        int x=que.front();que.pop();
        book[x]=false;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i],z=1;
            if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z;
                if(!book[y])
                {
                    que.push(y);
                    book[y]=true;
                    if(++c[y]>n) return;
                }
            }
        }
    }
    int Max=0;
    for(int i=1;i<=n;i++)
    	Max=max(Max,dis[i]);
    ans=max(ans,Max);
}
int getf(int x) {return f[x]==x?x:f[x]=getf(f[x]);}
void merge(int x,int y) {f[getf(y)]=getf(x);}
int main()
{
//	ios::sync_with_stdio(false);
	while(~scanf("%d",&n)&&n)
	{
		ans=0;
		init();
		for(int i=1;i<=n;i++) f[i]=i;
		for(int i=1;i<=n;i++)
		{
			string str;
			cin>>str;
			t[str]=i;
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			string str1,str2;
			cin>>str1>>str2;
			int u=t[str1],v=t[str2];
			merge(u,v);
			add(u,v);
			add(v,u);
		}
		bool Flag=false;
		int ss=getf(1);
		for(int i=1;i<=n;i++)
		{
			if(getf(i)!=ss)
			{
				Flag=true;
				break;
			}
		}
		if(Flag)
		{
			puts("-1");
			continue; 
		}
		for(int i=1;i<=n;i++)
			spfa(i);
		printf("%d
",ans);
	}
	return 0; 
}