LOJ116 有源汇有上下界最大流(上下界网络流)

  考虑有源汇上下界可行流:由汇向源连inf边,那么变成无源汇图,按上题做法跑出可行流。此时该inf边的流量即为原图中该可行流的流量。因为可以假装把加上去的那些边的流量放回原图。

  此时再从原来的源向原来的汇跑最大流。超源超汇相关的边已经流满不会再退流,则下界可以满足,并且在此基础上增广是可以保证原图的流量平衡的。求出的最大流即为原图最大流。因为显然原图最大流=可行流流量+原图新增流量,而可行流流量等于汇到源流量,这部分在跑最大流的时候被退流并计入答案。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 210
#define M 50000
#define S 0
#define T 201
#define inf 1000000000
int n,m,w,v,t=-,p[N],degree[N],l[M],tot=;
int cur[N],d[N],q[N],ans=;
struct data{int to,nxt,cap,flow;
}edge[M];
void addedge(int x,int y,int z)
{
t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=,p[x]=t;
t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=,edge[t].flow=,p[y]=t;
}
bool bfs(int s,int t)
{
memset(d,,sizeof(d));d[s]=;
int head=,tail=;q[]=s;
do
{
int x=q[++head];
for (int i=p[x];~i;i=edge[i].nxt)
if (d[edge[i].to]==-&&edge[i].flow<edge[i].cap)
{
d[edge[i].to]=d[x]+;
q[++tail]=edge[i].to;
}
}while (head<tail);
return ~d[t];
}
int work(int k,int f,int t)
{
if (k==t) return f;
int used=;
for (int i=cur[k];~i;i=edge[i].nxt)
if (d[k]+==d[edge[i].to])
{
int w=work(edge[i].to,min(f-used,edge[i].cap-edge[i].flow),t);
edge[i].flow+=w,edge[i^].flow-=w;
if (edge[i].flow<edge[i].cap) cur[k]=i;
used+=w;if (used==f) return f;
}
if (used==) d[k]=-;
return used;
}
void dinic(int s,int t)
{
while (bfs(s,t))
{
memcpy(cur,p,sizeof(p));
ans+=work(s,inf,t);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("loj116.in","r",stdin);
freopen("loj116.out","w",stdout);
const char LL[]="%I64d";
#else
const char LL[]="%lld";
#endif
n=read(),m=read(),w=read(),v=read();
memset(p,,sizeof(p));
for (int i=;i<=m;i++)
{
int x=read(),y=read(),low=read(),high=read();
addedge(x,y,high-low);
degree[y]+=low,degree[x]-=low;
l[i]=low;
}
for (int i=;i<=n;i++)
if (degree[i]>) addedge(S,i,degree[i]),tot+=degree[i];
else if (degree[i]<) addedge(i,T,-degree[i]);
addedge(v,w,inf);
dinic(S,T);
if (ans<tot) cout<<"please go home to sleep";
else ans=,dinic(w,v),cout<<ans;
return ;
}
上一篇:js按钮点击事件


下一篇:iOS 定位系统 知识