锐客网

  1. 首页 > it技术 > >

Codeforces Round #349 (Div. 2) D. World Tour

思维

题意： 给出n个点m条边的有向图, 每条边的长度为1
要求找出四个点a,b,c,d使得 a->b + b->c + c->d 的距离最大 其中a->b ,b->c ,c->d代表两点之间的最短路径
(1<=n<=3000) (1<=m<=5000)

思路
因为时间给了 5 秒，所以枚举其中的两个点肯定没问题，但是再多枚举一个点都是不可能的了。那么我们就枚举两个点。枚举哪两个点呢？先考虑枚举起点和终点。不过即使枚举出起点和终点，我们也很难求出中间的点，因为变化实在太多（如果只走三个点的话这样枚举或许是可行的）。然后再考虑枚举中间两个点。假设枚举到的中间两个点为 i,j ，那么如果能求出到i点距离最远的点和j点能到达的最远的点（根据题意两点之间“距离”表示的是两点之间的最短路径长度），这样枚举就是可行的。我们可以通过BFS （不需要用 Dijkstra 或 SPFA ，因为每条边的长度都是相同的）预处理求出任意两点之间的最短路径长度。然后对于每个点得到两个序列 d1,d2 ， d1[i] 表示所有能够到达 i 的不是i的点按照到i的距离从大到小排序得到的序列， d2[i] 表示所有从 i 出发能够到达的不是i的点按照i到它的距离从大到小排序得到的序列。那么，为什么要求出这么个序列而不是直接求距离最大的点呢？因为题目要求的4 个点不能重复。也就是说，如果我们求出到中间两点距离最大的两个点 s,t ，那么 s,t 可能会和 i,j 发生重复。因此我们应该得到 d1,d2 序列。对于我们枚举出的点 i,j ，再枚举 d1[i] 和 d2[j] 中的点 ii 和 jj 各 3 个。为什么只枚举 3 个点呢？因为 i,j 是两个点。只有枚举 3 个点才能保证至少有一个点不与 i,j 重复（其实我觉得为了防止 s,t 重复至少应该枚举 4 个点，但是 3 个点也 AC 了）。最后就可以根据 ii?i?j?jj 这条路径的长度更新最长路径了。

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define L(i) i<<1 #define R(i) i<<1|1 #define INF0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-9 #define maxn 10010 #define MOD 1000000007struct Edge { int to,next; }edge[maxn]; int n,m; int tot,head[maxn],vis[maxn]; int dis[3030][3030]; vector【Codeforces Round #349 (Div. 2) D. World Tour】 > d1[maxn],d2[maxn]; void init() { tot = 0; memset(head,-1,sizeof(head)); } void add_edge(int u,int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } void bfs(int u) { queue q; q.push(u); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i != -1; i = edge[i].next) { int y = edge[i].to; if(dis[u][y] || y == u) continue; dis[u][y] = dis[u][x] + 1; q.push(y); } } }int main() { int t,C = 1; //scanf("%d",&t); while(scanf("%d%d",&n,&m) != EOF) { init(); for(int i = 0; i < m; i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y); } memset(dis,0,sizeof(dis)); for(int i = 1; i <= n; i++) bfs(i); for(int i = 1; i <= n; i++) { d1[i].clear(); d2[i].clear(); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(!dis[i][j]) continue; d2[i].push_back(make_pair(dis[i][j],j)); d1[j].push_back(make_pair(dis[i][j],i)); } for(int i = 1; i <= n; i++) { sort(d1[i].rbegin(),d1[i].rend()); sort(d2[i].rbegin(),d2[i].rend()); } int ans = 0; int v1,v2,v3,v4; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(!dis[i][j]) continue; for(int ii = 0; ii < min(4,(int)d1[i].size()); ii++) for(int jj = 0; jj < min(4,(int)d2[j].size()); jj++) { int u = d1[i][ii].second; int v = d2[j][jj].second; if(u == j || i == v || !dis[u][v]) continue; if(dis[u][i] + dis[i][j] + dis[j][v] > ans) { ans = dis[u][i] + dis[i][j] + dis[j][v]; v1 = u; v2 = i; v3 = j; v4 = v; } } } //printf("%d\n",ans); printf("%d %d %d %d\n",v1,v2,v3,v4); } return 0; }



    推荐阅读


    上一篇：MFC|MFC 循环界面假死的解决(MFC 按钮终止循环)

    下一篇：轻量级的EventBus简单实现