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;}