网络流（Dinic算法）学习笔记

二分图匹配里的好多题解都是网络流啊……水完二分图匹配的dfs版我决定学习一下垂涎已久的网络流（雾） 参考博客：[EK不够快？ 再学个Dinic吧 by 钱逸凡](https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-jiang-xie-zhi-dinic) [Dinic算法 by SYCstudio](https://www.cnblogs.com/SYCstudio/p/7260613.html) 参考书籍：刘汝佳《算法竞赛入门经典第二版》 网络流：在一个**有向图**上选择一个**源点s**、一个**汇点t**。源点只流出，汇点只流进。同时，一条边(u,v)有的**流量**记为**f(u,v)**,也有**最大流量**称为**容量**,记为**c(u,v)**。（若该边不存在，则c(u,v)==0）。一条边上的剩余流量（没有用完的）称为**残量**，即 容量-流量 。除了源点和汇点，同一时间所有的边的流量应该是相等的 基本性质： 1. $f(u,v)\le c(u,v)$**（容量限制）** 2. 对于任何一个不是源点或汇点的点u,总有$$\sum_{p\in E}f(p,u)=\sum_{q\in E}f(u,q)$$ **因为入流和出流相等（斜对称性）** 3. 对于任何一条有向边(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，**（流量平衡）**$$\sum_{(u,v)\in E}f(u,v)=0$$（这些f中有些是负数） 从s运送出来的物品数目等于到达t的物品数目，而这正是此处最大化的目标 ——紫书 对于增广路： 算法思想：从零流（所有边的流量均为0）开始不断增加流量，保持每次增加流量后都满足以上性质。计算每条边上的殘量，得到**殘量网络**（注意殘量网络中的边数，可能达到原图中边数的两倍，因为加上了反边）。增广路算法基于：殘量网络中任何一条从s到t的有向道路都对应一条原图中的增广路——只要求出该道路中所有殘量的最小值d，把对应的所有边上的流量减去d，在答案里加上d即可，这个过程称为**增广** **显然只要殘量网络中存在增广路，流量就可以增大；反之，如果不存在增广路，流量就已经最大。（增广路定理）** 但是如果一条一条地找出增广路，万一有一些极（毒）端（瘤）数据（比如几条相邻的边容量相差特别大），这个时间复杂度就是无法承受的。Dinic算法的高效之处在于它能够同时找出几条增广路：运用**分层图** 具体怎么实现呢？ >Dinic算法分为两个步骤： 1. bfs分层 2. dfs增广 3. 重复执行1.2直到图中无增广路为止 > by 钱逸凡 一些小细节： 1. 存图的时候要从偶数开始存，同时存正向边和反向边（这样就可以保证正向边编号全为偶数，反向边编号为i^1（奇偶性相反）） 2. 反向边怎么用？因为找到的增广路不一定是最优的，反边给你“反悔”的机会。如果这条边边权为0，那么往回走的时候并不会对流量有所影响（走不回去）。所以一开始反边的边权应该存0，当正向边减去**所有残量的最小量d**（此时这个值已经被加入到了答案）的时候，反向边应该加上d（因为对于源点和汇点来说中间流量的这些变化都是无差别的，为了保证反向正向相加得原边权，不改变原本的条件就得这么做） 来吧！上代码！ ```cpp #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; } ```