给出一个有向图,以及src和dst。判断是否存在从src到dst的两条路径,使得除了src和dst外,没有其它点同时属于两条路径。
给每个点一个为1的点容量(src和dst为2),边的容量也是1,然后判断最大流是否大于等于2.
收获:
边不能重复:将点拆成两个点考虑,然后考虑匹配。
点不能重复:给每个点一个点容量(其实还是拆点),然后考虑流。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define maxn 620
#define oo 0x3f3f3f3f
#define eps 1e-10
using namespace std; int sg( double x ) {
return (x>-eps)-(x<eps);
}
struct Edge {
int u, v, f;
Edge( int u, int v, int f ):u(u),v(v),f(f){}
};
struct Dinic {
int n, src, dst;
vector<Edge> edge;
vector<int> g[maxn];
int dep[maxn], cur[maxn]; void init( int n, int src, int dst ) {
this->n = n;
this->src = src;
this->dst = dst;
for( int u=; u<=n; u++ )
g[u].clear();
edge.clear();
}
void add_edge( int u, int v, int f ) {
g[u].push_back( edge.size() );
edge.push_back( Edge(u,v,f) );
g[v].push_back( edge.size() );
edge.push_back( Edge(v,u,) );
}
bool bfs() {
queue<int> qu;
memset( dep, , sizeof(dep) );
qu.push( src );
dep[src] = ;
while( !qu.empty() ) {
int u=qu.front();
qu.pop();
for( int t=; t<g[u].size(); t++ ) {
Edge &e = edge[g[u][t]];
if( e.f && !dep[e.v] ) {
dep[e.v] = dep[e.u]+;
qu.push( e.v );
}
}
}
return dep[dst];
}
int dfs( int u, int a ) {
if( u==dst || a== ) return a;
int remain=a, past=, na;
for( int &t=cur[u]; t<g[u].size(); t++ ) {
Edge &e=edge[g[u][t]];
Edge &ve=edge[g[u][t]^];
if( dep[e.v]==dep[e.u]+ && e.f && (na=dfs(e.v,min(e.f,remain))) ) {
remain -= na;
past += na;
e.f -= na;
ve.f += na;
if( remain== ) break;
}
}
return past;
}
int maxflow() {
int flow = ;
while( bfs() ) {
memset( cur, , sizeof(cur) );
flow += dfs(src,oo);
}
return flow;
}
}; int n;
double freq[maxn];
int xx[maxn], yy[maxn], rr[maxn];
vector<int> g[maxn];
Dinic D; bool cross( int i, int j ) {
int dx = xx[i]-xx[j];
int dy = yy[i]-yy[j];
int sr = rr[i]+rr[j];
return dx*dx+dy*dy <= sr*sr;
}
int main() {
int T;
scanf( "%d", &T );
while( T-- ) {
scanf( "%d", &n );
int src, dst;
for( int i=; i<=n; i++ ) {
scanf( "%lf%d%d%d", freq+i, xx+i, yy+i, rr+i );
if( sg(freq[i]-789.0)== ) dst=i;
if( sg(freq[i]-400.0)== ) src=i;
}
for( int i=; i<=n; i++ ) {
g[i].clear();
for( int j=; j<=n; j++ )
if( cross(i,j) && sg(freq[i]-freq[j])< ) {
g[i].push_back( j );
}
}
D.init( n+n, src, dst );
for( int u=; u<=n; u++ ) {
D.add_edge( u, u+n, +(u==src) );
for( int t=; t<g[u].size(); t++ ) {
int v=g[u][t];
if( u==src && v==dst )
D.add_edge( u+n, v, oo );
else
D.add_edge( u+n, v, );
}
}
int flow = D.maxflow();
bool ok = flow>=;
printf( "Game is %s\n", ok ? "VALID" : "NOT VALID" );
}
}