给出一个有向图，以及src和dst。判断是否存在从src到dst的两条路径，使得除了src和dst外，没有其它点同时属于两条路径。
给每个点一个为1的点容量（src和dst为2），边的容量也是1，然后判断最大流是否大于等于2.
收获：
边不能重复：将点拆成两个点考虑，然后考虑匹配。
点不能重复：给每个点一个点容量（其实还是拆点），然后考虑流。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <vector> 5 #define maxn 620 6 #define oo 0x3f3f3f3f 7 #define eps 1e-10 8 using namespace std; 9 10 int sg( double x ) { 11 return (x>-eps)-(x<eps); 12 } 13 struct Edge { 14 int u, v, f; 15 Edge( int u, int v, int f ):u(u),v(v),f(f){} 16 }; 17 struct Dinic { 18 int n, src, dst; 19 vector<Edge> edge; 20 vector<int> g[maxn]; 21 int dep[maxn], cur[maxn]; 22 23 void init( int n, int src, int dst ) { 24 this->n = n; 25 this->src = src; 26 this->dst = dst; 27 for( int u=1; u<=n; u++ ) 28 g[u].clear(); 29 edge.clear(); 30 } 31 void add_edge( int u, int v, int f ) { 32 g[u].push_back( edge.size() ); 33 edge.push_back( Edge(u,v,f) ); 34 g[v].push_back( edge.size() ); 35 edge.push_back( Edge(v,u,0) ); 36 } 37 bool bfs() { 38 queue<int> qu; 39 memset( dep, 0, sizeof(dep) ); 40 qu.push( src ); 41 dep[src] = 1; 42 while( !qu.empty() ) { 43 int u=qu.front(); 44 qu.pop(); 45 for( int t=0; t<g[u].size(); t++ ) { 46 Edge &e = edge[g[u][t]]; 47 if( e.f && !dep[e.v] ) { 48 dep[e.v] = dep[e.u]+1; 49 qu.push( e.v ); 50 } 51 } 52 } 53 return dep[dst]; 54 } 55 int dfs( int u, int a ) { 56 if( u==dst || a==0 ) return a; 57 int remain=a, past=0, na; 58 for( int &t=cur[u]; t<g[u].size(); t++ ) { 59 Edge &e=edge[g[u][t]]; 60 Edge &ve=edge[g[u][t]^1]; 61 if( dep[e.v]==dep[e.u]+1 && e.f && (na=dfs(e.v,min(e.f,remain))) ) { 62 remain -= na; 63 past += na; 64 e.f -= na; 65 ve.f += na; 66 if( remain==0 ) break; 67 } 68 } 69 return past; 70 } 71 int maxflow() { 72 int flow = 0; 73 while( bfs() ) { 74 memset( cur, 0, sizeof(cur) ); 75 flow += dfs(src,oo); 76 } 77 return flow; 78 } 79 }; 80 81 int n; 82 double freq[maxn]; 83 int xx[maxn], yy[maxn], rr[maxn]; 84 vector<int> g[maxn]; 85 Dinic D; 86 87 bool cross( int i, int j ) { 88 int dx = xx[i]-xx[j]; 89 int dy = yy[i]-yy[j]; 90 int sr = rr[i]+rr[j]; 91 return dx*dx+dy*dy <= sr*sr; 92 } 93 int main() { 94 int T; 95 scanf( "%d", &T ); 96 while( T-- ) { 97 scanf( "%d", &n ); 98 int src, dst; 99 for( int i=1; i<=n; i++ ) { 100 scanf( "%lf%d%d%d", freq+i, xx+i, yy+i, rr+i ); 101 if( sg(freq[i]-789.0)==0 ) dst=i; 102 if( sg(freq[i]-400.0)==0 ) src=i; 103 } 104 for( int i=1; i<=n; i++ ) { 105 g[i].clear(); 106 for( int j=1; j<=n; j++ ) 107 if( cross(i,j) && sg(freq[i]-freq[j])<0 ) { 108 g[i].push_back( j ); 109 } 110 } 111 D.init( n+n, src, dst ); 112 for( int u=1; u<=n; u++ ) { 113 D.add_edge( u, u+n, 1+(u==src) ); 114 for( int t=0; t<g[u].size(); t++ ) { 115 int v=g[u][t]; 116 if( u==src && v==dst ) 117 D.add_edge( u+n, v, oo ); 118 else 119 D.add_edge( u+n, v, 1 ); 120 } 121 } 122 int flow = D.maxflow(); 123 bool ok = flow>=2; 124 printf( "Game is %s ", ok ? "VALID" : "NOT VALID" ); 125 } 126 }