hdu4460 Friend Chains

题目链接

把每个人抽象成点，每个朋友关系抽象成边，这样问题就变为了求各个点的最短路中最长的一条。

首先想到的是类似树的直径的方法，跑两遍BFS，第一遍找离1号点最远的点u，第二遍找离点u最远的点v，点u和点v之间的距离就是答案。可是，交上去之后，你会看到一行大字：Time Limit Exceeded。

于是，我们换一种方法：跑n次Dijkstra，第i次求出所有点到点i的距离，然后用一个变量Max记录每次最远的距离，然后用一个变量ans记录最大的Max，最后输出ans。交上去之后，你又会看到熟悉的一行字：Time Limit Exceeded。

But，将Dijkstra改为SPFA就过了……（据说把Dijkstra换成BFS也能过）太玄学了吧……

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\n",ans);
    }
    return 0; 
}

hdu4460 Friend Chains

原文：https://www.cnblogs.com/juruo-zzt/p/12268201.html