题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4183
题意：
T个测试数据
n个圆
下面 fre x y r 表示圆的频率 坐标和半径
要求：
从频率为400(最小的) 圆 走到频率为789(最大)的圆，再走回来，除起点每个点只能经过一次
问这样的路径是否存在
走法：从400->789时经过的圆频率只增不减， 只能走相交的圆
反之则频率只减不增，也只能走相交的圆
建图：
以789为源点， 400为汇点
其他点拆点拆成2个点，自己连自己，cap=1表示这个点只能走一次
然后跑一遍最大流，当汇点流>=2时说明有这样的路径
如果从起点可以连接到终点，那就肯定可以满足要求。
收获：
dinic用stack的新写法！感觉相比搜索的写法有些优化，因为没有了一些没什么价值的递归！
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int maxn = 605; const int inf = 0x3f3f3f3f; int n, eid; int head[maxn], lev[maxn]; struct Point { double fre; int x, y, r; }p[maxn], s, t; struct Edge { int from, to, cap, nxt; Edge(){} Edge(int fro, int t, int c, int nx):from(fro), to(t), cap(c), nxt(nx){} }edge[5005]; bool Cross(Point n1, Point n2) { return (n1.x - n2.x)*(n1.x - n2.x) + (n1.y - n2.y)*(n1.y - n2.y) < (n1.r + n2.r)*(n1.r + n2.r); } inline void init() { eid = 0; memset(head, -1, sizeof(head)); } inline void AddEdge(int u, int v, int cap) { edge[eid] = Edge(u, v, cap, head[u]); head[u] = eid++; } bool BFS(int from, int to) { memset(lev, -1, sizeof(lev)); lev[from] = 0; queue<int> q; q.push(from); while(!q.empty()) { int u = q.front();q.pop(); for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to; if(lev[v] == -1 && edge[i].cap > 0) { lev[v] = lev[u] + 1; q.push(v); } } } if(lev[to] != -1) return true; return false; } int Stack[maxn], cur[maxn], top; int dinic(int from, int to) { int ans = 0; while(BFS(from, to)) { memcpy(cur, head, sizeof(head)); int u = from, top = 0; while(true) { if(u == to) { int flow = inf, loc;//loc 表示 Stack 中 cap 最小的边 for(int i = 0; i < top; i++) if(flow > edge[Stack[i]].cap) { flow = edge[Stack[i]].cap; loc = i; } for(int i = 0; i < top; i++) { edge[Stack[i]].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]].from;//从最受限制的边所连的点继续增广 } for(int i = cur[u]; i != -1; cur[u] = i = edge[i].nxt)//cur[u] 表示u所在能增广的边的下标 if(edge[i].cap && (lev[u] + 1 == lev[edge[i].to])) break; if(cur[u] != -1) { Stack[top++] = cur[u]; u = edge[cur[u]].to; } else { if(top == 0) break; lev[u] = -1; u = edge[Stack[--top]].from; } } } return ans; } int main() { int T; cin >> T; while(T--) { cin >> n; for(int i = 1; i <= n; i++) { cin >> p[i].fre >> p[i].x >> p[i].y >> p[i].r; if(p[i].fre == 400) s = p[i], i--, n--; else if(p[i].fre == 789) t = p[i], i--, n--; } if(Cross(s, t)) { printf("Game is VALID\n"); continue; } init(); for(int i = 1; i <= n; i++) { AddEdge(i, i+n, 1); AddEdge(n+i, i, 0); if(Cross(p[i], s)) { AddEdge(0, i, 1); AddEdge(i, 0, 0); } if(Cross(p[i], t)) { AddEdge(i+n, 2*n+1, 1); AddEdge(2*n+1, i+n, 0); } for(int j = i+1; j <= n; j++) if(Cross(p[i], p[j])) { if(p[i].fre > p[j].fre) { AddEdge(j+n, i, 1); AddEdge(i, j+n, 0); } else { AddEdge(i+n, j, 1); AddEdge(j, i+n, 0); } } } int ans = dinic(0, 2*n+1); if(ans < 2) printf("Game is NOT VALID\n"); else printf("Game is VALID\n"); } return 0; }
