题意：若干个区域 每个区域有一个值 区域是圆 给出圆心和半径
从起点（值为400.0）到终点（值为789.0）满足走相交的圆 并且值必须递增 然后从终点到起点 值必须递减 此外区域只能去一次
思路：建图 相互能走的区域连一条边 因为只能走一次 所以拆点 如果没有来回 只有去 那么判断最大流为1即可
现在还要回来 并且回来的条件和去的条件想法（一个递增一个递减）可以反向考虑给源点cap=2 最大流为2
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 610;
const int INF = 999999999;
struct Edge
{
int from, to, cap, flow;
Edge(){}
Edge(int from, int to, int cap, int flow) : from(from), to(to), cap(cap), flow(flow){}
};
struct Point
{
double d, x, y, r;
Point(){}
Point(double d, double x, double y, double r) : d(d), x(x), y(y), r(r){}
}a[maxn];
int n, m, s, t;
vector <Edge> edges;
vector <int> G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];void AddEdge(int from, int to, int cap)
{
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BFS()
{
memset(vis, 0, sizeof(vis));
queue <int> Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while(!Q.empty())
{
int x = Q.front(); Q.pop();
for(int i = 0; i < G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if(!vis[e.to] && e.cap > e.flow)
{
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x, int a)
{
if(x == t || a == 0)
return a;
int flow = 0, f;
for(int& i = cur[x]; i < G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0)
{
e.flow += f;
edges[G[x][i]^1].flow -= f;
flow += f;
a -= f;
if(a == 0)
break;
}
}
return flow;
}
int Maxflow()
{
int flow = 0;
while(BFS())
{
memset(cur, 0, sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
bool ok(int i, int j)
{
if(a[i].d >= a[j].d)
return false;
if((a[i].r + a[j].r)*(a[i].r + a[j].r) > (a[i].x - a[j].x)*(a[i].x - a[j].x)+(a[i].y - a[j].y)*(a[i].y - a[j].y))
return true;
return false;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int k;
scanf("%d", &k);
n = k*2;
edges.clear();
for(int i = 0; i < n; i++)
G[i].clear();
for(int i = 0; i < k; i++)
{
scanf("%lf %lf %lf %lf", &a[i].d, &a[i].x, &a[i].y, &a[i].r);
if(a[i].d == 400.0)
s = i;
if(a[i].d == 789.0)
t = i;
}
for(int i = 0; i < k; i++)
{
if(i != s && i != t)
AddEdge(i<<1, i<<1|1, 1);
for(int j = 0; j < i; j++)
{
if(ok(i, j))
{
AddEdge(i<<1|1, j<<1, 1);
}
else if(ok(j, i))
{
AddEdge(j<<1|1, i<<1, 1);
}
}
}
AddEdge(s<<1, s<<1|1, 2);
s = s<<1;
t = t<<1;
//printf("%d %d\n", s, t);
if(Maxflow() >= 2)
puts("Game is VALID");
else
puts("Game is NOT VALID");
}
return 0;
}
HDU 4183 Pahom on Water 来回走不重复点的网络流,布布扣,bubuko.com
HDU 4183 Pahom on Water 来回走不重复点的网络流
原文：http://blog.csdn.net/u011686226/article/details/25245465