听说网络流的时代要来临了
在有向图\(G(V,E)\)中：
仅有一个入度为\(0\)的点\(S\)，称为源点
仅有一个出度为\(0\)的点\(T\)，称为汇点
每条边权值非负，称为该边的容量，记作\(c(u,v)\)
弧的流量：容量网络中每条边的实际流量,记作\(f(u,v)\)
网络流：容量网络中所有弧上流量的集合\(f={f(u,v)}\)
残量网络：所有点和没有满流的边构成的图被称为残量网络
增广路：残量网络中从源点\(S\)到汇点\(T\)的路径被称为增广路
零流：网络流上每条弧上流量都为\(0\)
伪流：只满足容量限制，不满足流守恒的网络流（据说预流推进有用）
1.容量限制：每条边的实际流量\(f(u,v)\)不超过它的容量\(c(u,v)\)，\(c(u,v)-f(u,v)\)被称为剩余流量
2.斜对称：\(f(u,v)=-f(v,u)\)
3.流守恒：除了源点和汇点之外，其余各点流入和流出的流量相等
基本思想：通过\(BFS\)不断寻找增广路并添加回流求出最大流
首先我们解释怎么进行回流：
现在我们有一个画的很丑的网络流图……
我们在上面添加反向边，边权全部为0：
然后通过bfs找增广路，假设找到了蓝色这一条：
\(emm\)我们发现路径上最小流量为\(1\),我们把答案\(+1\)，把蓝色路线上的流量全部\(-1\)，然后就没法继续增广了
但是显然答案应该是\(2\)啊
这时我们应该将路线上反向边流量\(+1\)
此时我们继续寻找增广路，会发现另外一条
再将答案\(+1\)就得到正确结果了
我们发现对于中间那条边，我们正向流过一次，反向流过一次，然后流量恢复到了初始时刻的状态
也就是说反向边给了网络流一个反悔的机会，可以让边上的流量退回到以前的状态，相当于让两条本不应该交叉的增广路变成合法状态
可以证明：每次增广都会使得流量增加，且增加次数与流量大小无关，是多项式级别的复杂度
其实EK算法复杂度上界是\(O(nm^2)\)，实际复杂度一般达不到上界
但是\(EK\)算法复杂度仍然有点高，最高可达\(O(n^5)\)，我们对其进行优化
观察到在\(EK\)算法中我们每次寻找一条增广路，效率较低，我们尝试每次寻找多条增广路
\(Dinic\)算法是在残量网络的分层图上\(DFS\)寻找增广路的算法
规定节点的层是该点到源点的最短距离，原图中所有的点和连接不同层的点之间的边（未饱和弧）构成的子图称为分层图
我们每次用\(BFS\)在残量网络上构造分层图，然后通过\(DFS\)在分层图上寻找增广路。改变流量过程与\(EK\)算法一致，直到无法找到新的增广路为止
理论复杂度上界为\(O(n^2m)\)，但是法律规定不许卡dinic
但是某谷的模板题\(n^2m\)上界达到\(10^{13}\)也有点过分了吧
```cpp
#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=10010,inf=0x3f3f3f3f;
int n,m,e,ret,tim,st,ed;
int head[N],cnt=1;//记得从1开始，不然异或一下就变成0了
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<<5];
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 dis[N];
queue q;
inline bool bfs()
{
memset(dis,0,sizeof(dis));//分层
q.push(st);dis[st]=1;//初始不赋成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(!dis[t]&&a[i].val)//下个点没被分过层且这条弧还有用
{
dis[t]=dis[now]+1;
q.push(t);
}
}
}
return dis[ed];
}
inline int dfs(int now,int c)
{
if(now==ed||!c) return c;//到达汇点或者没流量了
int ret=c,f;
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(dis[t]==dis[now]+1)
{
f=dfs(t,min(ret,a[i].val));
ret-=f;
a[i].val-=f;
a[i^1].val+=f;
if(!ret) return c;//当前流量流完了
}
}
if(ret==c) dis[now]=0;//废点,没法增广
return c-ret;
}
inline int dinic()
{
int ret=0;
while(bfs()) ret+=dfs(st,inf);
return ret;
}
inline void main()
{
n=read(),m=read(),st=read(),ed=read();
for(int x,y,z,i=1;i<=m;++i)
{
x=read(),y=read(),z=read();
link(x,y,z);
}
printf("%lld\n",dinic());
}
}
signed main()
{
red::main();
return 0;
}
```
考虑我们\(dfs\)的过程必然是将某一条边榨干之后再返回，所以这条边其实已经没有用了，我们下次不需要再访问
增加cur数组，每次\(BFS\)的时候赋值成\(head\)
for(int i=1;i<=n;++i)
{
dis[i]=0;
cur[i]=head[i];
}然后\(DFS\)的时候再记录
for(int i=cur[now];i;i=a[i].nxt)
{
cur[now]=i;
int t=a[i].to;
if(dis[t]==dis[now]+1)
{
f=dfs(t,min(ret,a[i].val));
ret-=f;
a[i].val-=f;
a[i^1].val+=f;
if(!ret) return c;//当前流量流完了
}
}
最大流一般用来构造一个图然后判断是否满足某些条件，如果最大流达到某个数值说明满足
已知图\(G(V,E)\)是网络流图，假设\(g\)是\(V\)的一个子集，而且\(g\)满足：\(S\in g,T\notin g\)，这样\(g\)把顶点分成两部分
鸽割的定义：起点在\(g\)，终点在\(\overline{g}\)的边，所组成的集合，为割，记作\((g,\overline{g})\)
\((g,\overline{g})\)中所有边容量的集合称为割的容量，记作\(C(g,\overline{g})\)
网络流的最大流等于最小割的容量
证明：不会
但是可以感性理解一下：最大流由增广路上容量最小的边限制，而最小割必定是由所有割中容量之和最小的一组割构成
原文：https://www.cnblogs.com/knife-rose/p/12094721.html