题意：给你一张有向图，叫你给出四个点的序列a,b,c,d，使得这四个点依次间的最短路之和最大。(4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000)
思路：O(n4)可用来对拍
我们需要O（n2）级别的算法
若枚举c,d，预处理出x到b比较远的3个x，d到y比较远的3个y，时间复杂度O(9n2)
为什么是3个而不是2个？
abc已枚举，若d的备选是ab就要GG，所以应该多一个备用，也就是三个点
1 var c,d:array[1..3000,1..3,1..2]of longint; 2 head,vet,next,b,flag,q,x,y:array[1..10000]of longint; 3 dis:array[1..3000]of longint; 4 save:array[1..3000,1..3000]of longint; 5 n,m,tot,i,s1,s2,s3,s4,a1,b1,c1,d1,ans,j,k,s,p1,q1:longint; 6 7 procedure add(a,b:longint); 8 begin 9 inc(tot); 10 next[tot]:=head[a]; 11 vet[tot]:=b; 12 head[a]:=tot; 13 end; 14 15 procedure bfs(x:longint); 16 var t,w,e,u,v:longint; 17 begin 18 fillchar(b,sizeof(b),0); 19 fillchar(dis,sizeof(dis),0); 20 t:=1; w:=1; q[1]:=x; b[x]:=1; dis[x]:=0; 21 while t<=w do 22 begin 23 u:=q[t]; inc(t); 24 e:=head[u]; 25 while e<>0 do 26 begin 27 v:=vet[e]; 28 if b[v]=0 then 29 begin 30 dis[v]:=dis[u]+1; 31 b[v]:=1; 32 inc(w); q[w]:=v; 33 end; 34 e:=next[e]; 35 end; 36 end; 37 end; 38 39 begin 40 //assign(input,'1.in'); reset(input); 41 //assign(output,'1.out'); rewrite(output); 42 readln(n,m); 43 for i:=1 to m do 44 begin 45 readln(x[i],y[i]); 46 add(x[i],y[i]); 47 end; 48 49 for i:=1 to n do 50 begin 51 bfs(i); 52 k:=1; s:=0; 53 fillchar(flag,sizeof(flag),0); 54 for j:=1 to n do 55 if (flag[j]=0)and(dis[j]>s) then 56 begin 57 k:=j; s:=dis[j]; 58 end; 59 flag[k]:=1; c[i,1,1]:=k; c[i,1,2]:=s; 60 k:=1; s:=0; 61 for j:=1 to n do 62 if (flag[j]=0)and(dis[j]>s) then 63 begin 64 k:=j; s:=dis[j]; 65 end; 66 flag[k]:=1; c[i,2,1]:=k; c[i,2,2]:=s; 67 k:=1; s:=0; 68 for j:=1 to n do 69 if (flag[j]=0)and(dis[j]>s) then 70 begin 71 k:=j; s:=dis[j]; 72 end; 73 flag[k]:=1; c[i,3,1]:=k; c[i,3,2]:=s; // x---->c[i] 1,2,3 74 for j:=1 to n do save[i,j]:=dis[j]; 75 end; 76 77 fillchar(head,sizeof(head),0); 78 tot:=0; 79 for i:=1 to m do add(y[i],x[i]); 80 81 for i:=1 to n do 82 begin 83 bfs(i); 84 k:=1; s:=0; 85 fillchar(flag,sizeof(flag),0); 86 for j:=1 to n do 87 if (flag[j]=0)and(dis[j]>s) then 88 begin 89 k:=j; s:=dis[j]; 90 end; 91 flag[k]:=1; d[i,1,1]:=k; d[i,1,2]:=s; 92 k:=1; s:=0; 93 for j:=1 to n do 94 if (flag[j]=0)and(dis[j]>s) then 95 begin 96 k:=j; s:=dis[j]; 97 end; 98 flag[k]:=1; d[i,2,1]:=k; d[i,2,2]:=s; 99 k:=1; s:=0; 100 for j:=1 to n do 101 if (flag[j]=0)and(dis[j]>s) then 102 begin 103 k:=j; s:=dis[j]; 104 end; 105 flag[k]:=1; d[i,3,1]:=k; d[i,3,2]:=s; // d[i] 1 2 3 ---->i 106 end; 107 108 s1:=1; s2:=2; s3:=3; s4:=4; ans:=-maxlongint; 109 for b1:=1 to n do 110 for c1:=1 to n do 111 if save[b1,c1]>0 then 112 for p1:=1 to 3 do 113 for q1:=1 to 3 do 114 begin 115 d1:=c[c1,p1,1]; 116 a1:=d[b1,q1,1]; //a1-->b1-->c1-->d1 117 if (a1<>b1)and(a1<>c1)and(a1<>d1)and(b1<>c1)and(b1<>d1)and(c1<>d1) then 118 if d[b1,q1,2]+c[c1,p1,2]+save[b1,c1]>ans then 119 begin 120 s1:=a1; s2:=b1; s3:=c1; s4:=d1; 121 ans:=d[b1,q1,2]+c[c1,p1,2]+save[b1,c1]; 122 end; 123 end; 124 writeln(s1,' ',s2,' ',s3,' ',s4); 125 126 //close(input); 127 //close(output); 128 end.