2012 Asia Hangzhou Regional Contest-hdu4460Friend Chains(SPFA)

2012 Asia Hangzhou Regional Contest--hdu4460Friend Chains(SPFA)

题目请戳这里

题目大意：给n个人，m个关系，组成了一张关系网，求一个k使任意2个人在关系网中距离不大于k。

题目分析：

12年杭州现场赛四大水题之一。

就是在无向图中求出任意2点距离最小值，取最小值的最大值为k。任意2点最小值很容易想到floyd，不过此题的点数达到1000，O(n^3)压力山大。所以可以做n个spfa。枚举起点跑n次spfa，一次spfa时间复杂度大约O(ke)，所以总的时间复杂度就是O(nke)，k一般比较小，可以承受。

不过跑的不是很快。。。

详情请见代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<string>
using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const double PI = acos(-1.0);
typedef __int64 ll;
const int N = 1001;
const int M = 10005;

map<string,int>lcm;
int ans;
int n,m,num;
struct node
{
    int to,next,dis;
}g[M + M];
int head[N],que[N];
string a,b;
int dist[N];
bool flag[N];
void build(int s,int e,int v)
{
    g[num].to = e;
    g[num].dis = v;
    g[num].next = head[s];
    head[s] = num ++;
}

void spfa(int st)
{
    memset(flag,false,sizeof(flag));
    int i,front,rear;
    memset(dist,0x3f,sizeof(dist));
    front = rear = 0;
    flag[st] = true;
    dist[st] = 0;
    que[rear ++] = st;
    while(front != rear)
    {
        int u = que[front ++];
        flag[u] = false;
        if(front == N)
            front = 0;
        for(i = head[u];~i;i = g[i].next)
        {
            int v = g[i].to;
            if(dist[v] > dist[u] + g[i].dis)
            {
                dist[v] = dist[u] + g[i].dis;
                if(flag[v] == false)
                {
                    flag[v] = true;
                    que[rear ++] = v;
                    if(rear == N)
                        rear = 0;
                }
            }
        }
    }
    for(i = 1;i <= n;i ++)
    {
        if(i == st)
            continue;
        ans = max(ans,dist[i]);
    }
}
void gao()
{
    for(int i = 1;i <= n;i ++)
        spfa(i);
}

int main()
{
    int i;
    while(scanf("%d",&n),n)
    {
        memset(head,-1,sizeof(head));
        num = 1;
        lcm.clear();
        for(i = 1;i <= n;i ++)
        {
            cin>>a;
            lcm[a] = i;
        }
        scanf("%d",&m);
        while(m --)
        {
            cin>>a>>b;
            build(lcm[a],lcm[b],1);
            build(lcm[b],lcm[a],1);
        }
        ans = 0;
        gao();
        if(ans == inf)
            ans = -1;
        printf("%d\n",ans);
    }
    return 0;
}