題意：求兩條路 能從 400.0 -> 789.0 且這兩條路不想交（除了端點400，789 ）

求只能走一次的網絡流需要用到拆點，

將點i ?拆成 i 和 i+n ?i->i+n的容量為經過的次數 ?（這題為1 ）

若i 能到達 j ?則連接 i+n-> j

?

#include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <cmath> using namespace std; #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); typedef long long LL; const int MAXN = 514; const int MAXM = 40101; const int INF = 0x3f3f3f3f; const int mod = 1000000007; struct Edge {int to,next,cap,flow; } edge[MAXM]; //注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN]; void init() {tol = 0;memset(head,-1,sizeof (head)); } void addedge (int u,int v,int w,int rw = 0) {edge[tol].to = v;edge[tol].cap = w;edge[tol].flow = 0;edge[tol].next = head[u];head[u] = tol++;edge[tol].to = u;edge[tol].cap = rw;edge[tol].flow = 0;edge[tol].next = head[v];head[v] = tol++; } int Q[MAXN]; void BFS(int start,int end) {memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0] = 1;int front = 0, rear = 0;dep[end] = 0;Q[rear++] = end;while(front != rear){int u = Q[front++];for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i]. to;if(dep[v] != -1)continue;Q[rear++] = v;dep[v] = dep[u] + 1;gap[dep[v]]++;}} } int S[MAXN]; int sap(int start,int end, int N) {BFS(start,end);memcpy(cur,head,sizeof(head));int top = 0;int u = start;int ans = 0;int i;while(dep[start] < N){if(u == end){int Min = INF;int inser;for( i = 0; i < top; i++){if(Min > edge[S[i]].cap - edge[S[i]].flow){Min = edge[S[i]].cap - edge[S[i]].flow;inser = i;}}for( i = 0; i < top; i++){edge[S[i]]. flow += Min;edge[S[i]^1].flow -= Min;}ans += Min;top = inser;u = edge[S[top]^1].to;continue;}bool flag = false;int v;for( i = cur[u]; i != -1; i = edge[i]. next){v = edge[i]. to;if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){flag = true;cur[u] = i;break;}}if(flag){S[top++] = cur[u];u = v;continue;}int Min = N;for( i = head[u]; i != -1; i = edge[i].next){if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){Min = dep[edge[i].to];cur[u] = i;}}gap[dep[u]]--;if(!gap[dep[u]]) return ans;dep[u] = Min + 1;gap[dep[u]]++;if(u != start)u = edge[S[--top]^1].to;}return ans; } double gao(double x,double y,double a,double b) {return sqrt((x-a)*(x-a)+(y-b)*(y-b)); } struct point {double f,x,y,r;point(){}; }a[202]; bool cmp(point a,point b) {return a.f<b.f; } int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint t,n;scanf("%d",&t);while(t--){init();scanf("%d",&n);for(int i=0;i<n;i++)scanf("%lf%lf%lf%lf",&a[i].f,&a[i].x,&a[i].y,&a[i].r);sort(a,a+n,cmp);addedge(0,n,1);addedge(n-1,2*n-1,1);for(int i=0;i<n;i++){addedge(i,i+n,1);for(int j=i+1;j<n;j++){if(a[i].f<a[j].f&&gao(a[i].x,a[i].y,a[j].x,a[j].y)<(a[i].r+a[j].r))addedge(i+n,j,1);}}if(sap(0,2*n-1,2*n)==2)puts("Game is VALID");else puts("Game is NOT VALID");}return 0; }

轉載于:https://www.cnblogs.com/kewowlo/p/4088354.html

總結

以上是生活随笔為你收集整理的【网络流】 HDU 4183 Pahom on Water 拆点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。