首页 > 代码库 > 最大流最小割
最大流最小割
ZOJ Problem Set - 3792 Romantic Value http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5300
模板题，有两种统计边数的办法，一种是扩大边权flow*=mod，然后加flow+=1，最后的最小割就是flow/mod，最小割边数是flow%mod。
dinic
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<queue> 6 #define mt(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 const int inf=0x3f3f3f3f; 9 class Dinic { ///最大流(MV^2*ME) 10 typedef int typef;///流量的类型 11 static const int ME=4010;///边的个数 12 static const int MV=64;///点的个数 13 int temp[MV],cur[MV],level[MV],path[MV]; 14 bool used[MV]; 15 queue<int> q; 16 typef flow; 17 bool bfs(int s,int t) { 18 mt(level,-1); 19 while(!q.empty()) q.pop(); 20 q.push(s); 21 level[s]=1; 22 while(!q.empty()) { 23 int u=q.front(); 24 q.pop(); 25 for(int i=g.head[u]; ~i; i=g.e[i].next) { 26 int v=g.e[i].v; 27 if(level[v]==-1&&g.e[i].flow) { 28 level[v]=level[u]+1; 29 q.push(v); 30 if(v==t) return true; 31 } 32 } 33 } 34 return false; 35 } 36 struct G { 37 struct E { 38 int u,v,next; 39 typef flow; 40 } e[ME]; 41 int le,head[MV]; 42 void init() { 43 le=0; 44 mt(head,-1); 45 } 46 void add(int u,int v,typef flow) { 47 e[le].u=u; 48 e[le].v=v; 49 e[le].flow=flow; 50 e[le].next=head[u]; 51 head[u]=le++; 52 } 53 } g; 54 public: 55 typef getflow() { 56 return flow; 57 } 58 void init() { 59 g.init(); 60 } 61 void add(int u,int v,typef flow) { 62 g.add(u,v,flow); 63 g.add(v,u,0); 64 } 65 void solve(int s,int t) { 66 int p,tempp; 67 typef now; 68 bool flag; 69 flow=0; 70 while(bfs(s,t)) { 71 for(int i=0; i<MV; i++) { 72 temp[i]=g.head[i]; 73 used[i]=true; 74 } 75 p=1; 76 path[p]=s; 77 while(p) { 78 int u=path[p]; 79 if(u==t) { 80 now=inf; 81 for(int i=1; i<p; i++) { 82 now=min(now,g.e[cur[path[i]]].flow); 83 } 84 flow+=now; 85 for(int i=1; i<p; i++) { 86 int j=cur[path[i]]; 87 g.e[j].flow-=now; 88 g.e[j^1].flow+=now; 89 if(!g.e[j].flow) tempp=i; 90 } 91 p=tempp; 92 } else { 93 flag=false; 94 for(int i=temp[u]; ~i; i=g.e[i].next) { 95 int v=g.e[i].v; 96 if(used[v]&&g.e[i].flow&&level[u]+1==level[v]) { 97 cur[u]=i; 98 temp[u]=g.e[i].next; 99 flag=true;100 path[++p]=v;101 break;102 }103 }104 if(flag) continue;105 p--;106 used[u]=false;107 }108 }109 }110 }111 } dinic;112 int main() {113 int t,n,m,p,q,x,y,z;114 while(~scanf("%d",&t)) {115 while(t--) {116 scanf("%d%d%d%d",&n,&m,&p,&q);117 dinic.init();118 int sum=0;119 for(int i=0; i<m; i++) {120 scanf("%d%d%d",&x,&y,&z);121 dinic.add(x,y,z*2000+1);122 dinic.add(y,x,z*2000+1);123 sum+=z;124 }125 dinic.solve(p,q);126 int ans=dinic.getflow();127 int ans1 = ans/2000;//我是把边的权值乘以2000， 然后+1128 int ans2 = ans%2000;//这样%2000就是最小割的边数， /2000就是最小割了。129 if(ans == 0)printf("Inf\n");130 else printf("%.2f\n",(sum-ans1)*1.0/ans2);131 }132 }133 return 0;134 }
sap
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 class Sap { ///最大流 O(MV*ME^2) 8 typedef int typef;///流量的类型 9 static const int ME=4010;///边的个数 10 static const int MV=64;///点的个数 11 int n,dep[MV],gap[MV],cur[MV],S[MV],top,i,inser; 12 typef flow; 13 queue<int> q; 14 void bfs(int s,int t) { 15 mt(dep,-1); 16 mt(gap,0); 17 while(!q.empty()) q.pop(); 18 gap[0]=1; 19 dep[t]=0; 20 q.push(t); 21 while(!q.empty()) { 22 int u=q.front(); 23 q.pop(); 24 for(int i=g.head[u]; ~i; i=g.e[i].next) { 25 int v=g.e[i].v; 26 if(dep[v]!=-1) continue; 27 q.push(v); 28 dep[v]=dep[u]+1; 29 ++gap[dep[v]]; 30 } 31 } 32 } 33 struct G { 34 struct E { 35 int u,v,next; 36 typef flow; 37 } e[ME]; 38 int le,head[MV]; 39 void init() { 40 le=0; 41 mt(head,-1); 42 } 43 void add(int u,int v,typef flow) { 44 e[le].u=u; 45 e[le].v=v; 46 e[le].flow=flow; 47 e[le].next=head[u]; 48 head[u]=le++; 49 } 50 } g; 51 public: 52 void init(int tn) {///传入点的个数 53 n=tn; 54 g.init(); 55 } 56 void add(int u,int v,typef flow) { 57 g.add(u,v,flow); 58 g.add(v,u,0); 59 } 60 typef solve(int s,int t) { 61 bfs(s,t); 62 flow=top=0; 63 for(i=0;i<=n;i++) cur[i]=g.head[i]; 64 int u=s; 65 while(dep[s]<n) { 66 if(u==t) { 67 int temp=inf; 68 for(i=0; i<top; i++) 69 if(temp>g.e[S[i]].flow) { 70 temp=g.e[S[i]].flow; 71 inser=i; 72 } 73 for(i=0; i<top; i++) { 74 g.e[S[i]].flow-=temp; 75 g.e[S[i]^1].flow+=temp; 76 } 77 flow+=temp; 78 top=inser; 79 u=g.e[S[top]].u; 80 } 81 if(u!=t&&!gap[dep[u]-1]) break; 82 for(i=cur[u]; ~i; i=g.e[i].next) 83 if(g.e[i].flow&&dep[u]==dep[g.e[i].v]+1) 84 break; 85 if(~i) { 86 cur[u]=i; 87 S[top++]=i; 88 u=g.e[i].v; 89 } else { 90 int sma=n; 91 for(i=g.head[u]; ~i; i=g.e[i].next) { 92 if(!g.e[i].flow) continue; 93 int v=g.e[i].v; 94 if(sma>dep[v]) { 95 sma=dep[v]; 96 cur[u]=i; 97 } 98 } 99 --gap[dep[u]];100 dep[u]=sma+1;101 ++gap[dep[u]];102 if(u!=s) u=g.e[S[--top]].u;103 }104 }105 return flow;106 }107 }sap;108 int main() {109 int t,n,m,p,q,x,y,z;110 while(~scanf("%d",&t)) {111 while(t--) {112 scanf("%d%d%d%d",&n,&m,&p,&q);113 sap.init(n);114 int sum=0;115 for(int i=0; i<m; i++) {116 scanf("%d%d%d",&x,&y,&z);117 sap.add(x,y,z*2000+1);118 sap.add(y,x,z*2000+1);119 sum+=z;120 }121 int ans=sap.solve(p,q);122 int ans1 = ans/2000;//我是把边的权值乘以2000， 然后+1123 int ans2 = ans%2000;//这样%2000就是最小割的边数， /2000就是最小割了。124 if(ans == 0)printf("Inf\n");125 else printf("%.2f\n",(sum-ans1)*1.0/ans2);126 }127 }128 return 0;129 }
poj 1273 Drainage Ditches http://poj.org/problem?id=1273 and hdu1532 http://acm.hdu.edu.cn/showproblem.php?pid=1532
模板题。
dinic
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 class Dinic { ///最大流(MV^2*ME) 8 typedef int typef;///流量的类型 9 static const int ME=512;///边的个数 10 static const int MV=256;///点的个数 11 int temp[MV],cur[MV],level[MV],path[MV]; 12 bool used[MV]; 13 queue<int> q; 14 typef flow; 15 bool bfs(int s,int t) { 16 mt(level,-1); 17 while(!q.empty()) q.pop(); 18 q.push(s); 19 level[s]=1; 20 while(!q.empty()) { 21 int u=q.front(); 22 q.pop(); 23 for(int i=g.head[u]; ~i; i=g.e[i].next) { 24 int v=g.e[i].v; 25 if(level[v]==-1&&g.e[i].flow) { 26 level[v]=level[u]+1; 27 q.push(v); 28 if(v==t) return true; 29 } 30 } 31 } 32 return false; 33 } 34 struct G { 35 struct E { 36 int u,v,next; 37 typef flow; 38 } e[ME]; 39 int le,head[MV]; 40 void init() { 41 le=0; 42 mt(head,-1); 43 } 44 void add(int u,int v,typef flow) { 45 e[le].u=u; 46 e[le].v=v; 47 e[le].flow=flow; 48 e[le].next=head[u]; 49 head[u]=le++; 50 } 51 } g; 52 public: 53 typef getflow() { 54 return flow; 55 } 56 void init() { 57 g.init(); 58 } 59 void add(int u,int v,typef flow) { 60 g.add(u,v,flow); 61 g.add(v,u,0); 62 } 63 void solve(int s,int t) { 64 int p,tempp; 65 typef now; 66 bool flag; 67 flow=0; 68 while(bfs(s,t)) { 69 for(int i=0; i<MV; i++) { 70 temp[i]=g.head[i]; 71 used[i]=true; 72 } 73 p=1; 74 path[p]=s; 75 while(p) { 76 int u=path[p]; 77 if(u==t) { 78 now=inf; 79 for(int i=1; i<p; i++) { 80 now=min(now,g.e[cur[path[i]]].flow); 81 } 82 flow+=now; 83 for(int i=1; i<p; i++) { 84 int j=cur[path[i]]; 85 g.e[j].flow-=now; 86 g.e[j^1].flow+=now; 87 if(!g.e[j].flow) tempp=i; 88 } 89 p=tempp; 90 } else { 91 flag=false; 92 for(int i=temp[u]; ~i; i=g.e[i].next) { 93 int v=g.e[i].v; 94 if(used[v]&&g.e[i].flow&&level[u]+1==level[v]) { 95 cur[u]=i; 96 temp[u]=g.e[i].next; 97 flag=true; 98 path[++p]=v; 99 break;100 }101 }102 if(flag) continue;103 p--;104 used[u]=false;105 }106 }107 }108 }109 } dinic;110 int main(){111 int m,n,u,v,w;112 while(~scanf("%d%d",&m,&n)){113 dinic.init();114 while(m--){115 scanf("%d%d%d",&u,&v,&w);116 dinic.add(u,v,w);117 }118 dinic.solve(1,n);119 printf("%d\n",dinic.getflow());120 }121 return 0;122 }
sap
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 class Sap { ///最大流 O(MV*ME^2) 8 typedef int typef;///流量的类型 9 static const int ME=512;///边的个数 10 static const int MV=256;///点的个数 11 int n,dep[MV],gap[MV],cur[MV],S[MV],top,i,inser; 12 typef flow; 13 queue<int> q; 14 void bfs(int s,int t) { 15 mt(dep,-1); 16 mt(gap,0); 17 while(!q.empty()) q.pop(); 18 gap[0]=1; 19 dep[t]=0; 20 q.push(t); 21 while(!q.empty()) { 22 int u=q.front(); 23 q.pop(); 24 for(int i=g.head[u]; ~i; i=g.e[i].next) { 25 int v=g.e[i].v; 26 if(dep[v]!=-1) continue; 27 q.push(v); 28 dep[v]=dep[u]+1; 29 ++gap[dep[v]]; 30 } 31 } 32 } 33 struct G { 34 struct E { 35 int u,v,next; 36 typef flow; 37 } e[ME]; 38 int le,head[MV]; 39 void init() { 40 le=0; 41 mt(head,-1); 42 } 43 void add(int u,int v,typef flow) { 44 e[le].u=u; 45 e[le].v=v; 46 e[le].flow=flow; 47 e[le].next=head[u]; 48 head[u]=le++; 49 } 50 } g; 51 public: 52 void init(int tn) {///传入点的个数 53 n=tn; 54 g.init(); 55 } 56 void add(int u,int v,typef flow) { 57 g.add(u,v,flow); 58 g.add(v,u,0); 59 } 60 typef solve(int s,int t) { 61 bfs(s,t); 62 flow=top=0; 63 for(i=0;i<=n;i++) cur[i]=g.head[i]; 64 int u=s; 65 while(dep[s]<n) { 66 if(u==t) { 67 int temp=inf; 68 for(i=0; i<top; i++) 69 if(temp>g.e[S[i]].flow) { 70 temp=g.e[S[i]].flow; 71 inser=i; 72 } 73 for(i=0; i<top; i++) { 74 g.e[S[i]].flow-=temp; 75 g.e[S[i]^1].flow+=temp; 76 } 77 flow+=temp; 78 top=inser; 79 u=g.e[S[top]].u; 80 } 81 if(u!=t&&!gap[dep[u]-1]) break; 82 for(i=cur[u]; ~i; i=g.e[i].next) 83 if(g.e[i].flow&&dep[u]==dep[g.e[i].v]+1) 84 break; 85 if(~i) { 86 cur[u]=i; 87 S[top++]=i; 88 u=g.e[i].v; 89 } else { 90 int sma=n; 91 for(i=g.head[u]; ~i; i=g.e[i].next) { 92 if(!g.e[i].flow) continue; 93 int v=g.e[i].v; 94 if(sma>dep[v]) { 95 sma=dep[v]; 96 cur[u]=i; 97 } 98 } 99 --gap[dep[u]];100 dep[u]=sma+1;101 ++gap[dep[u]];102 if(u!=s) u=g.e[S[--top]].u;103 }104 }105 return flow;106 }107 }sap;108 int main(){109 int m,n,u,v,w;110 while(~scanf("%d%d",&m,&n)){111 sap.init(n);112 while(m--){113 scanf("%d%d%d",&u,&v,&w);114 sap.add(u,v,w);115 }116 printf("%d\n",sap.solve(1,n));117 }118 return 0;119 }
hdu 3549 Flow Problem http://acm.hdu.edu.cn/showproblem.php?pid=3549
模板
dinic
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 class Dinic { ///最大流(MV^2*ME) 8 typedef int typef;///流量的类型 9 static const int ME=2010;///边的个数 10 static const int MV=16;///点的个数 11 int temp[MV],cur[MV],level[MV],path[MV]; 12 bool used[MV]; 13 queue<int> q; 14 typef flow; 15 bool bfs(int s,int t) { 16 mt(level,-1); 17 while(!q.empty()) q.pop(); 18 q.push(s); 19 level[s]=1; 20 while(!q.empty()) { 21 int u=q.front(); 22 q.pop(); 23 for(int i=g.head[u]; ~i; i=g.e[i].next) { 24 int v=g.e[i].v; 25 if(level[v]==-1&&g.e[i].flow) { 26 level[v]=level[u]+1; 27 q.push(v); 28 if(v==t) return true; 29 } 30 } 31 } 32 return false; 33 } 34 struct G { 35 struct E { 36 int u,v,next; 37 typef flow; 38 } e[ME]; 39 int le,head[MV]; 40 void init() { 41 le=0; 42 mt(head,-1); 43 } 44 void add(int u,int v,typef flow) { 45 e[le].u=u; 46 e[le].v=v; 47 e[le].flow=flow; 48 e[le].next=head[u]; 49 head[u]=le++; 50 } 51 } g; 52 public: 53 typef getflow() { 54 return flow; 55 } 56 void init() { 57 g.init(); 58 } 59 void add(int u,int v,typef flow) { 60 g.add(u,v,flow); 61 g.add(v,u,0); 62 } 63 void solve(int s,int t) { 64 int p,tempp; 65 typef now; 66 bool flag; 67 flow=0; 68 while(bfs(s,t)) { 69 for(int i=0; i<MV; i++) { 70 temp[i]=g.head[i]; 71 used[i]=true; 72 } 73 p=1; 74 path[p]=s; 75 while(p) { 76 int u=path[p]; 77 if(u==t) { 78 now=inf; 79 for(int i=1; i<p; i++) { 80 now=min(now,g.e[cur[path[i]]].flow); 81 } 82 flow+=now; 83 for(int i=1; i<p; i++) { 84 int j=cur[path[i]]; 85 g.e[j].flow-=now; 86 g.e[j^1].flow+=now; 87 if(!g.e[j].flow) tempp=i; 88 } 89 p=tempp; 90 } else { 91 flag=false; 92 for(int i=temp[u]; ~i; i=g.e[i].next) { 93 int v=g.e[i].v; 94 if(used[v]&&g.e[i].flow&&level[u]+1==level[v]) { 95 cur[u]=i; 96 temp[u]=g.e[i].next; 97 flag=true; 98 path[++p]=v; 99 break;100 }101 }102 if(flag) continue;103 p--;104 used[u]=false;105 }106 }107 }108 }109 } dinic;110 int main() {111 int T,n,m,x,y,z;112 while(~scanf("%d",&T)){113 int cas=1;114 while(T--){115 scanf("%d%d",&n,&m);116 dinic.init();117 while(m--){118 scanf("%d%d%d",&x,&y,&z);119 dinic.add(x,y,z);120 }121 dinic.solve(1,n);122 printf("Case %d: %d\n",cas++,dinic.getflow());123 }124 }125 return 0;126 }
sap
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 class Sap { ///最大流 O(MV*ME^2) 8 typedef int typef;///流量的类型 9 static const int ME=2010;///边的个数 10 static const int MV=16;///点的个数 11 int n,dep[MV],gap[MV],cur[MV],S[MV],top,i,inser; 12 typef flow; 13 queue<int> q; 14 void bfs(int s,int t) { 15 mt(dep,-1); 16 mt(gap,0); 17 while(!q.empty()) q.pop(); 18 gap[0]=1; 19 dep[t]=0; 20 q.push(t); 21 while(!q.empty()) { 22 int u=q.front(); 23 q.pop(); 24 for(int i=g.head[u]; ~i; i=g.e[i].next) { 25 int v=g.e[i].v; 26 if(dep[v]!=-1) continue; 27 q.push(v); 28 dep[v]=dep[u]+1; 29 ++gap[dep[v]]; 30 } 31 } 32 } 33 struct G { 34 struct E { 35 int u,v,next; 36 typef flow; 37 } e[ME]; 38 int le,head[MV]; 39 void init() { 40 le=0; 41 mt(head,-1); 42 } 43 void add(int u,int v,typef flow) { 44 e[le].u=u; 45 e[le].v=v; 46 e[le].flow=flow; 47 e[le].next=head[u]; 48 head[u]=le++; 49 } 50 } g; 51 public: 52 void init(int tn) {///传入点的个数 53 n=tn; 54 g.init(); 55 } 56 void add(int u,int v,typef flow) { 57 g.add(u,v,flow); 58 g.add(v,u,0); 59 } 60 typef solve(int s,int t) { 61 bfs(s,t); 62 flow=top=0; 63 for(i=0;i<=n;i++) cur[i]=g.head[i]; 64 int u=s; 65 while(dep[s]<n) { 66 if(u==t) { 67 int temp=inf; 68 for(i=0; i<top; i++) 69 if(temp>g.e[S[i]].flow) { 70 temp=g.e[S[i]].flow; 71 inser=i; 72 } 73 for(i=0; i<top; i++) { 74 g.e[S[i]].flow-=temp; 75 g.e[S[i]^1].flow+=temp; 76 } 77 flow+=temp; 78 top=inser; 79 u=g.e[S[top]].u; 80 } 81 if(u!=t&&!gap[dep[u]-1]) break; 82 for(i=cur[u]; ~i; i=g.e[i].next) 83 if(g.e[i].flow&&dep[u]==dep[g.e[i].v]+1) 84 break; 85 if(~i) { 86 cur[u]=i; 87 S[top++]=i; 88 u=g.e[i].v; 89 } else { 90 int sma=n; 91 for(i=g.head[u]; ~i; i=g.e[i].next) { 92 if(!g.e[i].flow) continue; 93 int v=g.e[i].v; 94 if(sma>dep[v]) { 95 sma=dep[v]; 96 cur[u]=i; 97 } 98 } 99 --gap[dep[u]];100 dep[u]=sma+1;101 ++gap[dep[u]];102 if(u!=s) u=g.e[S[--top]].u;103 }104 }105 return flow;106 }107 }sap;108 int main() {109 int T,n,m,x,y,z;110 while(~scanf("%d",&T)){111 int cas=1;112 while(T--){113 scanf("%d%d",&n,&m);114 sap.init(n);115 while(m--){116 scanf("%d%d%d",&x,&y,&z);117 sap.add(x,y,z);118 }119 printf("Case %d: %d\n",cas++,sap.solve(1,n));120 }121 }122 return 0;123 }
csu 1433: Defend the Bases http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1433
二分图匹配。用最大流来求最大匹配数。先二分时间，就是二分答案，然后对于mid这个时间，可以建图跑看能否满流。
dinic
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<queue> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 const int inf=0x3f3f3f3f; 8 const int M=128; 9 const double eps=1e-12; 10 class Dinic { ///最大流(MV^2*ME) 11 typedef int typef;///流量的类型 12 static const int ME=M*M*2;///边的个数 13 static const int MV=M*M;///点的个数 14 int temp[MV],cur[MV],level[MV],path[MV]; 15 bool used[MV]; 16 queue<int> q; 17 typef flow; 18 bool bfs(int s,int t) { 19 mt(level,-1); 20 while(!q.empty()) q.pop(); 21 q.push(s); 22 level[s]=1; 23 while(!q.empty()) { 24 int u=q.front(); 25 q.pop(); 26 for(int i=g.head[u]; ~i; i=g.e[i].next) { 27 int v=g.e[i].v; 28 if(level[v]==-1&&g.e[i].flow) { 29 level[v]=level[u]+1; 30 q.push(v); 31 if(v==t) return true; 32 } 33 } 34 } 35 return false; 36 } 37 struct G { 38 struct E { 39 int u,v,next; 40 typef flow; 41 } e[ME]; 42 int le,head[MV]; 43 void init() { 44 le=0; 45 mt(head,-1); 46 } 47 void add(int u,int v,typef flow) { 48 e[le].u=u; 49 e[le].v=v; 50 e[le].flow=flow; 51 e[le].next=head[u]; 52 head[u]=le++; 53 } 54 } g; 55 public: 56 typef getflow() { 57 return flow; 58 } 59 void init() { 60 g.init(); 61 } 62 void add(int u,int v,typef flow) { 63 g.add(u,v,flow); 64 g.add(v,u,0); 65 } 66 void solve(int s,int t) { 67 int p,tempp; 68 typef now; 69 bool flag; 70 flow=0; 71 while(bfs(s,t)) { 72 for(int i=0; i<MV; i++) { 73 temp[i]=g.head[i]; 74 used[i]=true; 75 } 76 p=1; 77 path[p]=s; 78 while(p) { 79 int u=path[p]; 80 if(u==t) { 81 now=inf; 82 for(int i=1; i<p; i++) { 83 now=min(now,g.e[cur[path[i]]].flow); 84 } 85 flow+=now; 86 for(int i=1; i<p; i++) { 87 int j=cur[path[i]]; 88 g.e[j].flow-=now; 89 g.e[j^1].flow+=now; 90 if(!g.e[j].flow) tempp=i; 91 } 92 p=tempp; 93 } else { 94 flag=false; 95 for(int i=temp[u]; ~i; i=g.e[i].next) { 96 int v=g.e[i].v; 97 if(used[v]&&g.e[i].flow&&level[u]+1==level[v]) { 98 cur[u]=i; 99 temp[u]=g.e[i].next;100 flag=true;101 path[++p]=v;102 break;103 }104 }105 if(flag) continue;106 p--;107 used[u]=false;108 }109 }110 }111 }112 } dinic;113 struct G{114 double x,y,v;115 }jun[M],base[M];116 int main() {117 int n,m;118 while(~scanf("%d%d",&n,&m)) {119 for(int i=1; i<=n; i++) {120 scanf("%lf%lf%lf",&jun[i].x,&jun[i].y,&jun[i].v);121 }122 for(int i=1; i<=m; i++) {123 scanf("%lf%lf",&base[i].x,&base[i].y);124 }125 double L=0,R=inf;126 double ans=inf;127 while(L<=R) {128 int s=0,t=n+n+m;129 double mid=(L+R)/2;130 dinic.init();131 for(int i=1; i<=n; i++) {132 dinic.add(s,i,1);133 }134 for(int i=1; i<=m; i++) {135 dinic.add(n+i,t,1);136 }137 for(int i=1; i<=n; i++) {138 for(int j=1; j<=m; j++) {139 double dx=jun[i].x-base[j].x;140 double dy=jun[i].y-base[j].y;141 double dir=sqrt(dx*dx+dy*dy)/jun[i].v;142 if(dir<=mid) {143 dinic.add(i,n+j,1);144 }145 }146 }147 dinic.solve(s,t);148 if(dinic.getflow()==m) {149 ans=min(ans,mid);150 R=mid-eps;151 } else {152 L=mid+eps;153 }154 }155 printf("%.11f\n",ans);156 }157 return 0;158 }
sap
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<queue> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 const int inf=0x3f3f3f3f; 8 const int M=128; 9 const double eps=1e-12; 10 class Sap { ///最大流 O(MV*ME^2) 11 typedef int typef;///流量的类型 12 static const int ME=M*M*2;///边的个数 13 static const int MV=M*M;///点的个数 14 int n,dep[MV],gap[MV],cur[MV],S[MV],top,i,inser; 15 typef flow; 16 queue<int> q; 17 void bfs(int s,int t) { 18 mt(dep,-1); 19 mt(gap,0); 20 while(!q.empty()) q.pop(); 21 gap[0]=1; 22 dep[t]=0; 23 q.push(t); 24 while(!q.empty()) { 25 int u=q.front(); 26 q.pop(); 27 for(int i=g.head[u]; ~i; i=g.e[i].next) { 28 int v=g.e[i].v; 29 if(dep[v]!=-1) continue; 30 q.push(v); 31 dep[v]=dep[u]+1; 32 ++gap[dep[v]]; 33 } 34 } 35 } 36 struct G { 37 struct E { 38 int u,v,next; 39 typef flow; 40 } e[ME]; 41 int le,head[MV]; 42 void init() { 43 le=0; 44 mt(head,-1); 45 } 46 void add(int u,int v,typef flow) { 47 e[le].u=u; 48 e[le].v=v; 49 e[le].flow=flow; 50 e[le].next=head[u]; 51 head[u]=le++; 52 } 53 } g; 54 public: 55 void init(int tn) {///传入点的个数 56 n=tn; 57 g.init(); 58 } 59 void add(int u,int v,typef flow) { 60 g.add(u,v,flow); 61 g.add(v,u,0); 62 } 63 typef solve(int s,int t) { 64 bfs(s,t); 65 flow=top=0; 66 for(i=0;i<=n;i++) cur[i]=g.head[i]; 67 int u=s; 68 while(dep[s]<n) { 69 if(u==t) { 70 int temp=inf; 71 for(i=0; i<top; i++) 72 if(temp>g.e[S[i]].flow) { 73 temp=g.e[S[i]].flow; 74 inser=i; 75 } 76 for(i=0; i<top; i++) { 77 g.e[S[i]].flow-=temp; 78 g.e[S[i]^1].flow+=temp; 79 } 80 flow+=temp; 81 top=inser; 82 u=g.e[S[top]].u; 83 } 84 if(u!=t&&!gap[dep[u]-1]) break; 85 for(i=cur[u]; ~i; i=g.e[i].next) 86 if(g.e[i].flow&&dep[u]==dep[g.e[i].v]+1) 87 break; 88 if(~i) { 89 cur[u]=i; 90 S[top++]=i; 91 u=g.e[i].v; 92 } else { 93 int sma=n; 94 for(i=g.head[u]; ~i; i=g.e[i].next) { 95 if(!g.e[i].flow) continue; 96 int v=g.e[i].v; 97 if(sma>dep[v]) { 98 sma=dep[v]; 99 cur[u]=i;100 }101 }102 --gap[dep[u]];103 dep[u]=sma+1;104 ++gap[dep[u]];105 if(u!=s) u=g.e[S[--top]].u;106 }107 }108 return flow;109 }110 }sap;111 struct G{112 double x,y,v;113 }jun[M],base[M];114 int main() {115 int n,m;116 while(~scanf("%d%d",&n,&m)) {117 for(int i=1; i<=n; i++) {118 scanf("%lf%lf%lf",&jun[i].x,&jun[i].y,&jun[i].v);119 }120 for(int i=1; i<=m; i++) {121 scanf("%lf%lf",&base[i].x,&base[i].y);122 }123 double L=0,R=inf;124 double ans=inf;125 while(L<=R) {126 int s=0,t=n+n+m;127 double mid=(L+R)/2;128 sap.init(n+m+2);129 for(int i=1; i<=n; i++) {130 sap.add(s,i,1);131 }132 for(int i=1; i<=m; i++) {133 sap.add(n+i,t,1);134 }135 for(int i=1; i<=n; i++) {136 for(int j=1; j<=m; j++) {137 double dx=jun[i].x-base[j].x;138 double dy=jun[i].y-base[j].y;139 double dir=sqrt(dx*dx+dy*dy)/jun[i].v;140 if(dir<=mid) {141 sap.add(i,n+j,1);142 }143 }144 }145 if(sap.solve(s,t)==m) {146 ans=min(ans,mid);147 R=mid-eps;148 } else {149 L=mid+eps;150 }151 }152 printf("%.11f\n",ans);153 }154 return 0;155 }
end
最大流最小割
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。