题目链接： World Tour
题意： 给你一张有向图，叫你给出四个点的序列，使得这四个点依次间的最短路之和最大。
分析： n到3000，所以直接枚举四个点肯定超时，因此可以枚举b、c两个点，然后BFS预处理出能到b的最远的3个点，和c能到的最远的3个点。 之所以是3个点是因为，有可能备选点会和已定点重合，例如abc都定好了，然后d的备选是a、b，那就漏情况了，所以要备选3个点。
代码：
#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; #define maxn 5010 #define maxv 3010 const int inf=0x3f3f3f3f; struct edge { int v,next; } e[maxn]; struct node { int index,len; node() {} node(int x,int y):index(x),len(y) {} bool operator < (const node&A) { if(len==A.len) return index<A.index; return len<A.len; } } longestTo[maxv][3],longestFrom[maxv][3]; int dis[maxv][maxv],first[maxv]; bool inq[maxv]; int n,m,len; void UpdateFrom(node u,node v)//从u能到的最远的点 { longestFrom[u.index][0]=v; sort(longestFrom[u.index],longestFrom[u.index]+3); } void UpdateTo(node u,node v)//能到u的最远的点 { v.len=u.len; longestTo[u.index][0]=v; sort(longestTo[u.index],longestTo[u.index]+3); } void bfs(int x)//对每一个点寻找离它最远的三个点 { queue<node>Q; node st(x,0); Q.push(st); inq[x]=true; while(!Q.empty()) { node u=Q.front(); Q.pop(); for(int i=first[u.index]; ~i; i=e[i].next) { node v(e[i].v,u.len+1); if(!inq[v.index]) { inq[v.index]=true; UpdateFrom(st,v);//从st能到的最远的点 UpdateTo(v,st);//能到v的最远的点 dis[st.index][v.index]=v.len; Q.push(v); } } } } void add_edge(int u,int v)//邻接表存边 { e[len].v=v,e[len].next=first[u]; first[u]=len++; } int main() { memset(first,-1,sizeof(first)); memset(dis,inf,sizeof(dis)); scanf("%d%d",&n,&m); int u,v; len=0; for(int i=0; i<m; ++i) { scanf("%d%d",&u,&v); if(u==v) continue; add_edge(u,v); } for(int i=1; i<=n; ++i) { memset(inq,false,sizeof(inq)); bfs(i); } int ans[4]= {0}; int tot=0; for(int b=1; b<=n; ++b)//枚举两个点，寻找另外两个 for(int c=1; c<=n; ++c) for(int i=2; ~i; --i) for(int j=2; ~j; --j) { int a=longestTo[b][i].index; int d=longestFrom[c][j].index; if(a==b||a==c||a==d||b==c||b==d||c==d) continue; if(dis[a][b]==inf||dis[b][c]==inf||dis[c][d]==inf) continue; int tmp=dis[a][b]+dis[b][c]+dis[c][d]; if(tmp>tot) { tot=tmp; ans[0]=a; ans[1]=b; ans[2]=c; ans[3]=d; } } for(int i=0; i<4; ++i) printf("%d ",ans[i]); return 0; }总结：很强大的一道题，思路和代码都给了我很大启发。better
一开始我的想法是，先用最短路求出每两个点之间的最短距离，然后DFS枚举4个点。。。想想都超时啊。
参考博客： 初涉_代码世界
