题目链接：http://codeforces.com/problemset/problem/666/B
大意是给一张有向图，选取四个点，使得走这四个点，任意两个点之间走最短路，总距离最长。
3000个点直接floyd肯定不行，但是注意到任意每条路距离都是1，其实可以枚举所有源点作bfs，求出距离数组。
然后对于每个点求出以这个点为入点和出点距离最大的3个点。再根据这个信息，枚举四个点中的中间两个，再枚举这两个点距离他们最远的那3*3种情况，判断是否有重复，没有重复的话，更新答案。
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <string> 5 #include <cstring> 6 #include <cstdio> 7 #include <math.h> 8 #include <queue> 9 #include <stack> 10 #include <map> 11 #include <set> 12 using namespace std; 13 14 15 const int N=3005; 16 17 vector<int>edge[N]; 18 int dis[N][N]; 19 int n; 20 void bfs(int s) { 21 queue< pair<int,int> >que; 22 que.push(make_pair(s,0)); 23 dis[s][s]=0; 24 while (!que.empty()) { 25 pair<int,int> now=que.front(); 26 que.pop(); 27 int u=now.first,d=now.second; 28 for (int i=0;i<edge[u].size();i++) { 29 int v=edge[u][i]; 30 if (dis[s][v]>=0) continue; 31 dis[s][v]=d+1; 32 que.push(make_pair(v,d+1)); 33 } 34 } 35 } 36 pair<int,int> in[N][3],out[N][3]; 37 void upd(pair<int,int> x,pair<int,int> *y) { 38 for (int i=0;i<3;i++) { 39 if (x>y[i]) { 40 for (int j=2;j>i;j--) { 41 y[j]=y[j-1]; 42 } 43 y[i]=x; 44 break; 45 } 46 } 47 } 48 void solve() { 49 memset(dis,-1,sizeof dis); 50 for (int i=1;i<=n;i++){ 51 bfs(i); 52 for (int j=0;j<3;j++) { 53 in[i][j]=make_pair(-1,-1); 54 out[i][j]=make_pair(-1,-1); 55 } 56 } 57 for (int i=1;i<=n;i++) { 58 for (int j=1;j<=n;j++) { 59 if (i==j) continue; 60 if (dis[i][j]==-1) continue; 61 upd(make_pair(dis[i][j],i),in[j]); 62 upd(make_pair(dis[i][j],j),out[i]); 63 } 64 } 65 int best=0; 66 int a=-1,b=-1,c=-1,d=-1; 67 for (int i=1;i<=n;i++) { 68 for (int j=1;j<=n;j++) { 69 if (i==j) continue; 70 if (dis[i][j]==-1) continue; 71 for (int p=0;p<3;p++) { 72 if (in[i][p].first==-1) continue; 73 int ii=in[i][p].second; 74 if (ii==j) continue; 75 for (int q=0;q<3;q++) { 76 if (out[j][q].first==-1) continue; 77 int jj=out[j][q].second; 78 if (jj==i||jj==ii) continue; 79 80 int tot=dis[ii][i]+dis[i][j]+dis[j][jj]; 81 if (tot>best) { 82 best=tot; 83 a=ii;b=i;c=j;d=jj; 84 } 85 } 86 } 87 } 88 } 89 printf("%d %d %d %d ",a,b,c,d); 90 } 91 int main () { 92 int m; 93 scanf("%d %d",&n,&m); 94 for (int i=1;i<=m;i++) { 95 int u,v; 96 scanf("%d %d",&u,&v); 97 edge[u].push_back(v); 98 } 99 solve(); 100 return 0; 101 }