前置芝士
首先要比较清楚地了解网络最大流的原理以及(dinic)算法求最大流是过程
大力推荐博客liu_runda nb
无源汇上下界可行流
又称作循环流，这个网络流是没有源点和汇点的，只有流量在上面不停地循环
这个是其他上下界网络流的基础
(n)个点，(m)条边，每条边(e)有一个流量下界(low)和流量上界(up)，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。
两个限制一般会把自己搞掉，我们一个一个考虑，先考虑下界
只要我们先给每条弧都加一个(low)的流量下界这个限制就没了对吧，但是现在这个图很可能不满足流量平衡，我们姑且称当前图上的流量为初始流
我们应该在这张图上添加一个附加流，使得这个附加流加上初始流满足流量平衡
显然我们还要考虑上界，每条弧的附加流上限是(up-low)，所以我们建边的时候可以直接把容量设为(up-low)，把(low)提出来
考虑现在对于图中某个点(i),假设她现在的 总流入量-总流出量为(c_i)
那么如果这个(c_i)大于(0)，说明这个点她流入的流量有点多，应该流出一些（？
如果这个(c_i)小于(0)，说明她流出的太多了，应该注♂入♂灵♂魂♂
那这些多出来的和应该补充进入的流量怎么办呢？
我们可以设置虚拟源点和汇点
虚拟源点向每个(c_i>0)的点连边，容量为(c_i)
每个(c_i<0)的点向虚拟汇点连边，容量为(-c_i)
有人会疑惑为什么流入更多的还要流入，流出更多的还要流出吗？？？
因为我们并不是直接通过设置虚拟源点和汇点实现流量平衡的
虚拟源点和汇点的作用是：把刚开始不平衡的局面构造出来，然后通过(dinic)算法和原有的边实现流量平衡
如某个点(x)，它的(c_x>0)，那么我就从虚拟源点给他(c_x)的流，然后让这些流在原本的那些边上流动，直到流到某个(c_y<0)的点，通过这个(y)点流出
然后留在原有边上的流量是我们要求的附加流
如果我们能找到一个附加流加上初始流后流量守恒，那么直接与虚拟源点和虚拟汇点相连的边应该都满流
由于(sumlimits_{iin V}[c_i>0]c_i=-sumlimits_{iin V}[c_i<0]c_i)
所以如果能找到符合要求的附加流，那么在新图中的最大流应该等于(sumlimits_{iin V}[c_i>0]c_i)
求出最大流后怎么找到每条边的流量呢？
由于我们已经跑过(dinic)算法了，所以每条弧的反向弧中的流量就是这条弧所对应的附加流
展开查看
```cpp
#include
#include
#include
#include
#include
#include
using namespace std;
namespace red{
#define eps (1e-8)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=1e5+10,inf=0x3f3f3f3f;
int n,m,sum;
int st,ed;
int down[N];
int head[N],cnt=1;
struct point
{
int nxt,to,val;
point(){}
point(const int &nxt,const int &to,const int &val):nxt(nxt),to(to),val(val){}
}a[N];
int c[N];
inline void link(int x,int y,int z)
{
a[++cnt]=(point){head[x],y,z};head[x]=cnt;
a[++cnt]=(point){head[y],x,0};head[y]=cnt;
}
int d[N],cur[N];
queue q;
inline bool bfs()
{
for(int i=1;i<=n+2;++i)
{
d[i]=0;
cur[i]=head[i];
}
q.push(st);d[st]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(!d[t]&&a[i].val)
{
d[t]=d[now]+1;
q.push(t);
}
}
}
return d[ed];
}
inline int dfs(int now,int c)
{
if(now==ed||!c) return c;
int ret=c,f;
for(int i=cur[now];i;i=a[i].nxt)
{
cur[now]=i;
int t=a[i].to;
if(d[t]==d[now]+1)
{
f=dfs(t,min(a[i].val,ret));
a[i].val-=f;
a[i^1].val+=f;
ret-=f;
if(!ret) return c;
}
}
if(ret==c) d[now]=0;
return c-ret;
}
inline void dinic()
{
int ret=0;
while(bfs()) ret+=dfs(st,inf);
if(sum==ret)
{
puts("YES");
for(int i=3,j=1;j<=m;++j,i+=2)
{
printf("%d
",a[i].val+down[j]);
}
}
else puts("NO");
}
inline void main()
{
n=read(),m=read();
for(int x,y,up,i=1;i<=m;++i)
{
x=read(),y=read(),down[i]=read(),up=read();
link(x,y,up-down[i]);
c[y]+=down[i];
c[x]-=down[i];
}
st=n+1,ed=n+2;
for(int i=1;i<=n;++i)
{
if(c[i]>0) link(st,i,c[i]),sum+=c[i];
if(c[i]<0) link(i,ed,-c[i]);
}
dinic();
}
}
signed main()
{
red::main();
return 0;
}
```
有源汇上下界可行流
(n)个点，(m)条边，每条边(e)有一个流量下界(low)和流量上界(up)，给定源点(S)与汇点(T)，求源点到汇点的可行流。
这个东西就有点问题，因为(S)和(T)流量不守恒，刚刚我们处理的情况是所有节点流量守恒的情况
当然我们可以手动令它流量守恒，比如：由(T)向(S)连一条下界为(0)，上界为(inf)的边，就可以实现所有点流量守恒
然后重复刚才的过程，求一个循环流
然后把刚才加的那条边拆掉，我们就得到了一个有源汇上下界可行流
考虑这个有源汇上下界可行流的流量是多少？由于所有的流都会流入汇点，所以我们只要看最后(T)到(S)的反向弧中有多少流量
有源汇上下界最大流
(n)个点，(m)条边，每条边(e)有一个流量下界(low)和流量上界(up)，给定源点(S)与汇点(T)，求源点到汇点的最大流。
利用刚才的方法，我们已经求得了一个有源汇上下界可行流，那我们怎么得到有源汇上下界最大流？
由于目前我们的网络流中的流量已经平衡，所以我们只要在残量网络上再跑一个最大流即可
最终的最大流=有源汇上下界可行流+残量网络上最大流
考虑为什么不会超出上下界：
下界：我们在建图的时候下界并没有出现在原图中，下界是额外计算的，一定大于下界
上界：由于建边的时候流量为(up-low)，所以不会超过上界
其实实际操作起来很方便：只要先用虚拟源汇跑一遍(dinic)，然后不删除(T)到(S)的边，再用原本的源汇跑一遍(dinic)，得到的结果就是答案
为什么这样做是对的？
因为考虑第一次用虚拟源汇跑完(dinic)后，原图中留下的本就是残量网络
且原本的可行流应该保存在(T)到(S)的反向边中，然而我们这次跑的是(S)到(T)的最大流，这些流量刚好会被加上~
展开查看
```cpp
#include
#include
#include
#include
#include
#include
#include
using namespace std;
namespace red{
#define eps (1e-8)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=1e5+10,inf=0x3f3f3f3f;
int n,m,st,ed,stt,edd,ans,sum;
int c[N],x[N],y[N],low[N],up[N],e[N];
int head[N],cur[N],cnt=1;
struct point
{
int nxt,to,val;
point(){}
point(const int &nxt,const int &to,const int &val):nxt(nxt),to(to),val(val){}
}a[N];
inline void link(int x,int y,int z)
{
a[++cnt]=(point){head[x],y,z};head[x]=cnt;
a[++cnt]=(point){head[y],x,0};head[y]=cnt;
}
int d[N];
queue q;
inline bool bfs()
{
for(int i=1;i<=n+2;++i)
{
cur[i]=head[i];
d[i]=0;
}
q.push(stt);d[stt]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(!d[t]&&a[i].val)
{
d[t]=d[now]+1;
q.push(t);
}
}
}
return d[edd];
}
inline int dfs(int now,int c)
{
if(now==edd||!c) return c;
int ret=c,f;
for(int i=cur[now];i;i=a[i].nxt)
{
cur[now]=i;
int t=a[i].to;
if(d[t]==d[now]+1)
{
f=dfs(t,min(ret,a[i].val));
a[i].val-=f;
a[i^1].val+=f;
ret-=f;
if(!ret) return c;
}
}
if(ret==c) d[now]=0;
return c-ret;
}
inline void dinic()
{
int ret=0;
while(bfs()) ret+=dfs(stt,inf);
if(sum!=ret)
{
puts("please go home to sleep");
return;
}
stt=st,edd=ed;
while(bfs()) ans+=dfs(stt,inf);
printf("%d
",ans);
}
inline void main()
{
n=read(),m=read(),st=read(),ed=read();
for(int i=1;i<=m;++i)
{
x[i]=read(),y[i]=read(),low[i]=read(),up[i]=read();
link(x[i],y[i],up[i]-low[i]);
c[y[i]]+=low[i];
c[x[i]]-=low[i];
}
stt=n+1,edd=n+2;
for(int i=1;i<=n;++i)
{
if(c[i]>0) link(stt,i,c[i]),sum+=c[i];
if(c[i]<0) link(i,edd,-c[i]);
}
link(ed,st,inf);
dinic();
}
}
signed main()
{
red::main();
return 0;
}
```
有源汇上下界最小流
(n)个点，(m)条边，每条边(e)有一个流量下界(low)和流量上界(up)，给定源点(S)与汇点(T)，求源点到汇点的最小流。
思路完全类似，先求出有源汇上下界可行流
考虑在可行流基础上减去一个守恒的流量
需要深入理解(dinic)的反向边，我们如果找到一条从(T)到(S)的增广路，就说明去掉这条增广路上的流量，网络流仍然守恒
所以我们可以直接从(T)向(S)跑一波最大流，用可行流减去这次最大流的值，即为有源汇上下界最小流
注意这次不能留下那条(T)到(S)的(inf)边了(qwq)
上下界分析相同
展开查看
```cpp
#include
#include
#include
#include
#include
#include
#include
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=5e5+10,inf=0x3f3f3f3f3f3f3f3f;
int n,m,st,ed,stt,edd,ans,sum;
int c[N],x[N],y[N],low[N],up[N],e[N];
int head[N],cur[N],cnt=1;
struct point
{
int nxt,to,val;
point(){}
point(const int &nxt,const int &to,const int &val):nxt(nxt),to(to),val(val){}
}a[N];
inline void link(int x,int y,int z)
{
a[++cnt]=(point){head[x],y,z};head[x]=cnt;
a[++cnt]=(point){head[y],x,0};head[y]=cnt;
}
int d[N];
queue q;
inline bool bfs()
{
for(int i=1;i<=n+2;++i)
{
cur[i]=head[i];
d[i]=0;
}
q.push(stt);d[stt]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(!d[t]&&a[i].val)
{
d[t]=d[now]+1;
q.push(t);
}
}
}
return d[edd];
}
inline int dfs(int now,int c)
{
if(now==edd||!c) return c;
int ret=c,f;
for(int i=cur[now];i;i=a[i].nxt)
{
cur[now]=i;
int t=a[i].to;
if(d[t]==d[now]+1)
{
f=dfs(t,min(ret,a[i].val));
a[i].val-=f;
a[i^1].val+=f;
ret-=f;
if(!ret) return c;
}
}
if(ret==c) d[now]=0;
return c-ret;
}
inline void dinic()
{
int ret=0;
while(bfs()) ret+=dfs(stt,inf);
if(sum!=ret)
{
puts("please go home to sleep");
return;
}
ret=a[cnt].val;
stt=ed,edd=st;
for(int i=head[ed];i;i=a[i].nxt)
{
int t=a[i].to;
if(t==st) a[i].val=a[i^1].val=0;
}
while(bfs()) ans+=dfs(stt,inf);
printf("%lld
",ret-ans);
}
inline void main()
{
n=read(),m=read(),st=read(),ed=read();
for(int i=1;i<=m;++i)
{
x[i]=read(),y[i]=read(),low[i]=read(),up[i]=read();
link(x[i],y[i],up[i]-low[i]);
c[y[i]]+=low[i];
c[x[i]]-=low[i];
}
stt=n+1,edd=n+2;
for(int i=1;i<=n;++i)
{
if(c[i]>0) link(stt,i,c[i]),sum+=c[i];
if(c[i]<0) link(i,edd,-c[i]);
}
link(ed,st,inf);
dinic();
}
}
signed main()
{
red::main();
return 0;
}
```