微网站免费创建平台,有域名了如何自己做网站,学校网站建设开发方案书,装修公司需要什么资质考虑有源汇上下界可行流#xff1a;由汇向源连inf边#xff0c;那么变成无源汇图#xff0c;按上题做法跑出可行流。此时该inf边的流量即为原图中该可行流的流量。因为可以假装把加上去的那些边的流量放回原图。 此时再从原来的源向原来的汇跑最大流。超源超汇相关的边已经流… 考虑有源汇上下界可行流由汇向源连inf边那么变成无源汇图按上题做法跑出可行流。此时该inf边的流量即为原图中该可行流的流量。因为可以假装把加上去的那些边的流量放回原图。 此时再从原来的源向原来的汇跑最大流。超源超汇相关的边已经流满不会再退流则下界可以满足并且在此基础上增广是可以保证原图的流量平衡的。求出的最大流即为原图最大流。因为显然原图最大流可行流流量原图新增流量而可行流流量等于汇到源流量这部分在跑最大流的时候被退流并计入答案。 #includeiostream
#includecstdio
#includecmath
#includecstdlib
#includecstring
#includealgorithm
using namespace std;
int read()
{int x0,f1;char cgetchar();while (c0||c9) {if (c-) f-1;cgetchar();}while (c0c9) x(x1)(x3)(c^48),cgetchar();return x*f;
}
#define N 210
#define M 50000
#define S 0
#define T 201
#define inf 1000000000
int n,m,w,v,t-1,p[N],degree[N],l[M],tot0;
int cur[N],d[N],q[N],ans0;
struct data{int to,nxt,cap,flow;
}edge[M];
void addedge(int x,int y,int z)
{t;edge[t].toy,edge[t].nxtp[x],edge[t].capz,edge[t].flow0,p[x]t;t;edge[t].tox,edge[t].nxtp[y],edge[t].cap0,edge[t].flow0,p[y]t;
}
bool bfs(int s,int t)
{memset(d,255,sizeof(d));d[s]0;int head0,tail1;q[1]s;do{int xq[head];for (int ip[x];~i;iedge[i].nxt)if (d[edge[i].to]-1edge[i].flowedge[i].cap){d[edge[i].to]d[x]1;q[tail]edge[i].to;}}while (headtail);return ~d[t];
}
int work(int k,int f,int t)
{if (kt) return f;int used0;for (int icur[k];~i;iedge[i].nxt)if (d[k]1d[edge[i].to]){int wwork(edge[i].to,min(f-used,edge[i].cap-edge[i].flow),t);edge[i].floww,edge[i^1].flow-w;if (edge[i].flowedge[i].cap) cur[k]i;usedw;if (usedf) return f;}if (used0) d[k]-1;return used;
}
void dinic(int s,int t)
{while (bfs(s,t)){memcpy(cur,p,sizeof(p));answork(s,inf,t);}
}
int main()
{
#ifndef ONLINE_JUDGEfreopen(loj116.in,r,stdin);freopen(loj116.out,w,stdout);const char LL[]%I64d;
#elseconst char LL[]%lld;
#endifnread(),mread(),wread(),vread();memset(p,255,sizeof(p));for (int i1;im;i){int xread(),yread(),lowread(),highread();addedge(x,y,high-low);degree[y]low,degree[x]-low;l[i]low;}for (int i1;in;i)if (degree[i]0) addedge(S,i,degree[i]),totdegree[i];else if (degree[i]0) addedge(i,T,-degree[i]);addedge(v,w,inf);dinic(S,T);if (anstot) coutplease go home to sleep;else ans0,dinic(w,v),coutans;return 0;
} 转载于:https://www.cnblogs.com/Gloid/p/9420520.html
