网络流（Dinic算法）学习笔记
二分图匹配里的好多题解都是网络流啊……水完二分图匹配的dfs版我决定学习一下垂涎已久的网络流（雾）
参考博客：EK不够快？ 再学个Dinic吧 by 钱逸凡 Dinic算法 by SYCstudio
参考书籍：刘汝佳《算法竞赛入门经典第二版》
网络流：在一个有向图上选择一个源点s、一个汇点t。源点只流出，汇点只流进。同时，一条边(u,v)有的流量记为f(u,v),也有最大流量称为容量,记为c(u,v)。（若该边不存在，则c(u,v)==0）。一条边上的剩余流量（没有用完的）称为残量，即 容量-流量 。除了源点和汇点，同一时间所有的边的流量应该是相等的
基本性质：
-
- 对于任何一个不是源点或汇点的点u,总有
\sum_{p\in E}f(p,u)=\sum_{q\in E}f(u,q) 因为入流和出流相等（斜对称性） - 对于任何一条有向边(u,v),总有
f(u,v)=-f(v,u) 为什么呢？因为把3个物品从u运送到v后再把3个物品送回u是没有意义的，流量相当于0这样规定就好比“把3个物品从u运送v”等价于“把-3个物品从v运送到u”一样
——紫书
最大流经典例题：物资运送
最大流问题的目标是把最多的物品从s运送到t，而其他结点都只是中转，因此对于除了结点s和t以外的任意结点u，（流量平衡）
对于增广路：
算法思想：从零流（所有边的流量均为0）开始不断增加流量，保持每次增加流量后都满足以上性质。计算每条边上的殘量，得到殘量网络（注意殘量网络中的边数，可能达到原图中边数的两倍，因为加上了反边）。增广路算法基于：殘量网络中任何一条从s到t的有向道路都对应一条原图中的增广路——只要求出该道路中所有殘量的最小值d，把对应的所有边上的流量减去d，在答案里加上d即可，这个过程称为增广
显然只要殘量网络中存在增广路，流量就可以增大；反之，如果不存在增广路，流量就已经最大。（增广路定理）
但是如果一条一条地找出增广路，万一有一些极（毒）端（瘤）数据（比如几条相邻的边容量相差特别大），这个时间复杂度就是无法承受的。Dinic算法的高效之处在于它能够同时找出几条增广路：运用分层图
具体怎么实现呢？
Dinic算法分为两个步骤：
- bfs分层
- dfs增广
- 重复执行1.2直到图中无增广路为止
by 钱逸凡
一些小细节：
-
存图的时候要从偶数开始存，同时存正向边和反向边（这样就可以保证正向边编号全为偶数，反向边编号为i^1（奇偶性相反））
-
反向边怎么用？因为找到的增广路不一定是最优的，反边给你“反悔”的机会。如果这条边边权为0，那么往回走的时候并不会对流量有所影响（走不回去）。所以一开始反边的边权应该存0，当正向边减去所有残量的最小量d（此时这个值已经被加入到了答案）的时候，反向边应该加上d（因为对于源点和汇点来说中间流量的这些变化都是无差别的，为了保证反向正向相加得原边权，不改变原本的条件就得这么做）
来吧！上代码！
#include <cstdio>
#include <queue>
#include <cstring>
const int maxn=10000+10;
const int maxm=100000+10;
const int INF=0x7fffffff;
int head[maxn],nxt[maxm*2];//因为还要存反向边，所以要开两倍
int to[maxm*2],val[maxm*2];
int dep[maxn];
bool inque[maxn];
int n,m,s,t;
int tot=1,maxflow=0;
inline int min(int x,int y) {return x<y?x:y;}
void add(int u,int v,int w)//链式前向星存图
{
nxt[++tot]=head[u];
to[tot]=v;
val[tot]=w;
head[u]=tot;
}
void AddEdge()
{
int u,v,w;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
add(u, v, w);//正边
add(v, u, 0);//反边
}
}
bool bfs()//给增广路上的点分层
{
memset(dep, 0x3f3f3f3f, sizeof(dep));
memset(inque, 0, sizeof(inque));
dep[s]=0;//源点深度当然为0
std::queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inque[u]=0;//不在队伍中了
for (int i=head[u];i;i=nxt[i])
{
int v=to[i];//通向的点
if (val[i]&&dep[v]>dep[u]+1)//如果容量不为0且在u点之前还没有被搜到
{
dep[v]=dep[u]+1;
if (!inque[v])//如果点v不在当前队伍中
{
q.push(v);
inque[v]=1;
}
}
}
}
if (dep[t]!=0x3f3f3f3f)//只要汇点被搜到了，就还有增广路
return 1;
return 0;
}
int dfs(int pos,int low)//当前位置和最小残量，dfs用于寻找增广路
{
int rlow=0;
if (pos==t)//到达汇点
{
maxflow+=low;//直接将最大流更新
return low;//返回最小残量（当它为0时说明没有增广路了）
}
int used=0;//该点已经使用了的流量
for (int i=head[pos];i;i=nxt[i])
{
int v=to[i];
if (val[i]&&dep[v]==dep[pos]+1)//小优化：仅当v在当前位置的下一层中才进行查找是否有增广路
if (rlow=dfs(v, min(low-used, val[i])))//注意这里的min
{
used+=rlow;//该点使用的流量增加
val[i]-=rlow;
val[i^1]+=rlow;
if (used==low)//该点已达最大流量，不用继续找了
break;
}
}
return used;//返回该点已使用流量
}
int Dinic()
{
while(bfs())//如果还有增广路就继续dfs
dfs(s, INF);
return maxflow;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
AddEdge();
printf("%d\n",Dinic());
return 0;
}