Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 678 Accepted Submission(s): 312
这题题目意思很难看懂。。我看了好长时间也没看懂。。最终是从网上找的翻译。。我就在这翻译一下吧。
意思大约是：有多个点，每个点给出坐标与半径，加入两个点相交，就可以从这两个点走。题目要求先从起点到终点，再从终点回到起点。从起点到终点的过 程中，只能从频率小的走到频率大的点（前提是两点相交），从终点到起点的过程中，只能从频率大的走到频率小的。在走的过程中，除了起点与终点，别的只要走 过就会消失，就是说只能走一次。问可不可以从起点到终点又回到起点。
初一看没什么思路，后来一想，无非就是从起点到终点走两次，均是从小到大，而且中间经过的点不重复即可。然后建图就很简单了。为了保证每个点只走一 次，可以把权值设为1，这样每一步最多只能走一次。然后看最大流是否大于等于2即可。还有一点需要注意的是，如果可以直接从起点到终点的话，就不用判断 了，肯定可以满足要求。
#include<stdio.h> #include<string.h> #include<iostream> #include<queue> #include<algorithm> using namespace std; const int inf=0x7fffffff; int edge[500][500];//邻接矩阵 int dis[500];//距源点距离,分层图 int start,end; int m,n;//N:点数;M,边数 struct node{ double s; int x,y,r; }que[500]; bool con(int i,int j){ if(((que[i].x-que[j].x)*(que[i].x-que[j].x)+(que[i].y-que[j].y)*(que[i].y-que[j].y))<(que[i].r+que[j].r)*(que[i].r+que[j].r)) return true; else return false; } int maxflow, pre[500]; void Edmonds_Karp(int start, int end, int m){ while(1) { queue<int>p; int minflow = inf; p.push(start); memset(pre, 0, sizeof(pre)); while(!p.empty()){ int u = p.front(); p.pop(); if(u == end) break; for(int i = 1;i <= m;i++) if(edge[u][i] > 0&&pre[i] == 0){ pre[i] = u; p.push(i); } } if(pre[end] == 0) break; for(int i = end;i != start;i = pre[i]) minflow = min(minflow, edge[pre[i]][i]); for(int i = end;i != start;i = pre[i]) { edge[pre[i]][i] -= minflow; edge[i][pre[i]] += minflow; } maxflow+=minflow; } } int main(){ int t; scanf("%d",&t); while(t--){ memset(que,0,sizeof(que)); memset(edge,0,sizeof(edge)); int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf%d%d%d",&que[i].s,&que[i].x,&que[i].y,&que[i].r); } for(int i=1;i<=n;i++){ if(que[i].s==400.0){ start=i; } if(que[i].s==789.0){ end=i; } } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(con(i,j)){ if(que[i].s>que[j].s) edge[j][i]=1; else if(que[j].s>que[i].s) edge[i][j]=1; } } } maxflow = 0; Edmonds_Karp(start, end, n); if(maxflow>=2) printf("Game is VALID\n"); else printf("Game is NOT VALID\n"); } return 0; }
原文：http://www.cnblogs.com/13224ACMer/p/4729098.html