网络流（上下界可行流）
无源上下界可行流
一个有向图，可想而知从题目来说是没有源点汇点的，所以每一个点都都有入边和出边，那么我们把它转换为无下界的可行流在去求解，首先计算每一个节点的流出入的量，如果少流入大于少流出，我们建立虚拟源点汇点，少流入就补，少流出就出，因此在这个G’网络里我们会补充各个节点少流入出的流量，那么如果在边上允许这些流量的流入或流出同时从S流出的流量是满流那么就存在可行流量。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=210,M=1e5+10;
int head[N],idx=0;
int n,m,S,T;
int q[N],d[N],A[N],cur[N];
struct Edge{
int next,to,low,f;
}edge[M];
void add(int a,int b,int c,int d)
{
edge[idx]=(Edge){head[a],b,c,d-c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0,0},head[b]=idx++;
}
bool bfs()
{
memset(d,-1,sizeof d);
int tt=0,hh=0;
q[tt]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
cur[ver]=head[ver];
d[ver]=d[t]+1;
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(limit-flow,edge[i].f));
if(!t) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t; flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
int main()
{
memset(head,-1,sizeof head);
cin>>n>>m; S=0,T=n+1;
for(int i=1,a,b,c,d;i<=m;i++)
{
cin>>a>>b>>c>>d;
add(a,b,c,d);
A[a]-=c; A[b]+=c;
}
int tot=0;
for(int i=1;i<=n;i++)
if(A[i]>0) add(S,i,0,A[i]),tot+=A[i];
else if(A[i]<0) add(i,T,0,-A[i]);
if(dinic()!=tot) puts("NO");
else{
puts("YES");
for(int i=0;i<2*m;i+=2)
printf("%d\n",edge[i^1].f+edge[i].low);
}
return 0;
}有源上下界最大（小）流
在上题的基础上加上了源汇点，首先在s和t之间建立一条流量上界为inf下界为0的流量，那么用上述的做法做一遍dinic以后，在st残留网络的反向边中存储的就是原图s到t的流量，因为s会向T流出原图中s的下界，t会向S流入原图的下界，所以这一条边就平衡了原来流量；接下来删边同时做一遍s到t的dinic，就是最大流，反之即为最小流。如何证明一致性？首先原图G可以根据上述得到若干个G’，因为可能存在若干个最大流，设其中最大流f(st)，如果把两个最大流相减，会发现左右两边到ST的流量全部被删空了，因为全部都是满流，这样就剩下中间的一块s到t的可行流，我们把它给榨干就可以得出最终的结论了；反之对于一个可行流来说任意的st流量在相加的过程中，容量限制和流量守恒是保持的所以可以在不同的网络里面相互转化，G’最终转化到G，所以保持了一致性。
/*有源上下界最大流*/
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=220,M=1e5;
int n,m,S,T;
int q[N],d[N],cur[N],A[N];
int head[N],idx;
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(d,-1,sizeof d);
q[hh]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(limit-flow,edge[i].f));
if(!t) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
int main()
{
int s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
S=0,T=n+1;
memset(head,-1,sizeof head);
while(m--)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
add(a,b,d-c);
A[a]-=c; A[b]+=c;
}
int tot=0;
for(int i=1;i<=n;i++)
if(A[i]>0) add(S,i,A[i]),tot+=A[i];
else if(A[i]<0) add(i,T,-A[i]);
add(t,s,inf);
if(dinic()!=tot) puts("No Solution");
else{
int res=edge[idx-1].f;
S=s,T=t;
edge[idx-1].f=edge[idx-2].f=0;
printf("%d\n",res+dinic());
}
return 0;
}/*有源上下界最小流*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50010,M=1e6;
const int inf = 2147483647;
int n,m,S,T,idx=0;
int head[N],A[N],cur[N],d[N],q[N];
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(d,-1,sizeof d);
q[hh]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(limit-flow,edge[i].f));
if(!t) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
int main()
{
memset(head,-1,sizeof head);
int s,t;
cin>>n>>m>>s>>t;
S=0,T=n+1;
while(m--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,d-c);
A[a]-=c; A[b]+=c;
}
int tot=0;
for(int i=1;i<=n;i++)
if(A[i]>0) add(S,i,A[i]),tot+=A[i];
else if(A[i]<0) add(i,T,-A[i]);
add(t,s,inf);
if(tot!=dinic()) puts("No Solution");
else{
int res=edge[idx-1].f;
S=t,T=s;
edge[idx-1].f=edge[idx-2].f=0;
cout<<res-dinic();
}
return 0;
}
