概念
网络流 网络流是指给定一个有向图，其中有两个特殊的点：源点 (s)（Source）和汇点 (t)（Sink）；每条边都有一个指定的流量上限，即容量（Capacity），经过这条边的流量不能超过容量，这样的图被称为网络流图。同时，除了源点和汇点外，所有点的入流和出流都相等，源点只有流出的流，汇点只有流入的流，网络流就是从 (s) 到 (t) 的一个可行流。
可行流 定义 (c(u,v)) 为边 ((u,v)) 的容量，(f(u,v)) 表示边 ((u,v)) 的流量。若满足 (0le f(u,v)le c(u,v)) ，则称 (f(u,v)) 为边 ((u,v)) 上的流量。如果有一组流量满足：源点 (s) 的流入量等于整个网络的流量，汇点 (t) 的流出量等于整个网络的流量，除 (s) 和 (t) 外任意一点的流入量等于流出量。那么整个网络中的流量称为一个可行流。
最大流 在所有可行流中，流量最大的流称为最大流。
定义
- 源点 (s) ：只有流出量的点。
- 汇点 (t) ：只有流入量的点。
- 容量 (c) ：(c(u,v)) 表示边 ((u,v)) 上的容量。
- 流量 (f) ：(f(u,v)) 表示边 ((u,v)) 上的流量。
- 残量 (w) ：(w(u,v)) 表示边 ((u,v)) 上的残量，显然有 (w(u,v)=c(u,v)−f(u,v)) 。
性质
容量限制 对于任何一条边，都有 (0le f(u,v)le c(u,v)) 。
斜对称性 对于任何一条边，都有 (f(u,v)=−f(v,u)) 。即从 (u) 到 (v) 的流量一定等于从 (v) 到 (u) 的流量的相反数。
流守恒性 对于任何一个点 (u) ，如果满足 (u e s) 并且 (u e t) ，那么一定有 (sum f(u,v)=0) ，即 (u) 到相邻节点的流量之和为 (0) 。因为 (u) 本身不会制造和消耗流量。
求解
增广路
网络流算法的基本思想都是基于增广路的。朴素的增广路思想如下：
-
找到一条从 (s) 到 (t) 的路径，使得路径上的每一条边都有 (w(u,v)>0) 即残量大于 (0)。注意，这里是严格 (>) 而不是 (ge) ，这意味着这条边还可以分配流量。这条路径就被叫做増广路。
-
找到这条路径上最小的 (w(u,v)) ，记为 (flow) 。将这条路径上的每一条边的 (w(u,v)) 减去 (flow) 。
-
重复上述过程，直到找不到増广路为止。
上述方法并不是正确的网络流求解算法，没有考虑反悔操作，第一次选取的增广路并不一定是最优的。
反向边
改进 在朴素的增广路思想中，我们对正向边的 (w(u,v)) 减去 (flow) 的同时，将对应的反向边的 (w(v,u)) 加上 (flow) 。相当于可以反悔从这条边流过，即之前选取了这条边上的流量，我之后可以选择这条边上反向的流量，从而抵消之前非最优的流量选择。
初始时，每条边的 (w(u,v)=c(u,v)) ，它的反向边的 (w(v,u)=0) 。初始时，反向边不能有流量，因此残量为 (0) 。
算法思路总结
-
最初这个网络的流量为 (0) ，称为零流。
-
找到一条从 (s) 到 (t) 的路径，使得路径上的每一条边都有 (w(u,v)>0) 即残量大于 (0) 。注意：这里是严格 (>) 而不是 (ge) ，这意味着这条边还可以分配流量。这条路径就被叫做増广路。
-
找到这条路径上最小的 (w(u,v)) ，记为 (flow) 。
-
将这条路径上的每一条边的 (w(u,v)) 减去 (flow) ，同时将反向边 ((v,u)) 的 (w(v,u)) 加上 (flow) 。
-
重复上述过程，直到找不到増广路为止，此时的流量就是最大流。
算法
Edmonds-Karp
简称 ( ext{EK}) 算法，每次用 BFS 求出一条増广路径，通过记录每个点的前驱和这条边的编号来记录下这条路径。算法是对增广路思想的完全模拟。
复杂度爆炸
EK算法在有些情况下会被卡的很慢，比如如下情况：
其中 (w(2,3)=1)，其余正向边的 (w(u,v)=100) 。如果第一次増广路的策略不恰当，找到了 (1−2−3−4) ，那么 (w(2,3)=0) ，(w(3,2)=1) 。接下来又会找到増广路经 (1−3−2−4) ，然后又是 (1−2−3−4 dotsdots)
复杂度
( ext{EK}) 算法的时间复杂度为 (O(nm^2)) 。我们可以证明最多需要 (O(nm)) 次増广可以达到最大流，每次増广的复杂度为 (O(m)) 。绝大多数情况下这个复杂度都跑不满。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int N=1e4+5,M=2e5+5;
int n,m,s,t,tot=1,lnk[N],ter[M],nxt[M],val[M],pre[N],idx[N];
bool vis[N];
void add(int u,int v,int w) {
ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
bool bfs(int s,int t) {
memset(pre,0,sizeof(pre));
memset(vis,0,sizeof(vis));
std::queue<int> q;
q.push(s),vis[s]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=lnk[u];i;i=nxt[i]) {
int v=ter[i];
if(!vis[v]&&val[i]) {
pre[v]=u,idx[v]=i,q.push(v),vis[v]=1;
if(v==t) return 1;
}
}
}
return 0;
}
int EK(int s,int t) {
int ans=0;
while(bfs(s,t)) {
int mn=1<<30;
for(int i=t;i!=s;i=pre[i]) mn=std::min(mn,val[idx[i]]);
for(int i=t;i!=s;i=pre[i]) {
int x=idx[i];
val[x]-=mn,val[x^1]+=mn;
}
ans+=mn;
}
return ans;
}
int main() {
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w),add(v,u,0);
}
printf("%d
",EK(s,t));
return 0;
}
Dinic
算法实现
Dinic算法基于分层图的概念。
-
为了避免走重复的路径，从 (s) 开始 (BFS) 对图分层，将整个图分为若干层，其中 (s) 是第 (1) 层。如果一条边的残量为 (0) ，那么忽略这条无法増广的边。如果 (t) 的层数不为 (0) ，那么意味着存在増广路径。
-
如果存在増广路，那么从 (s) 开始进行 (DFS) 寻找从源点到汇点的増广路，注意此处増广必须要按照图的层次来遍历。每次下传当前流量 (flow)（初始流量认为是无穷大）。
-
设 (dep_i) 表示 (i) 的层次，(ans) 代表当前从 (u) 可以流的流量，对于当前点 (u) 相连的点 (v) ，如果 (dep_v=dep_u+1) 并且 (w(u,v)>0) ，那么可以増广。此时下传的 (flow) 应为 (min(w(u,v),flow−ans)) ，其中 (flow−ans) 代表从 (u) 还可以流的流量（已经有 (ans) 的流量从 (u) 已增广的分支流出去了）。当 (ans≥flow) 时意味着没有可以流的流量了，应该退出増广。
-
如果该 (DFS) 找到的可以増广的流量为 (0) ，表示增广失败，跳过这条边。否则将 (w(u,v)) 减去増广的流量，将 (w(v,u)) 和 (ans) 加上相同的值。
剪枝 如果遍历完所有的 (v) 后 (ans<flow) ，意味着已经从 (u) 流出了所有可以増广的流量，即 (u) 已经满流了，此时需要将 (dep_u) 设为 (−1) ，防止再次从这个点増广。
当前弧优化 每次 (DFS) 増广时不是从 (u) 出发的第 (1) 个点开始，而是用一个 (cnr) 数组记录点 (u) 増广到了哪条边，从这条边开始増广，以此来进一步加速。
复杂度
Dinic 算法的时间复杂度为 (O(n^2m)) 。我们可以证明最多需要建立 (O(n)) 个层次图，每次建立层次图的复杂度为 (O(m)) 。接下来分析 (DFS) 的复杂度，每次最多増广 (O(m)) 次，每次修改流量的复杂度为 (O(n)) ，所以 (DFS) 的复杂度为 (O(nm)) 。再加上 (O(n)) 个层次图，总复杂度为 (O(n^2m)) 。绝大多数情况下这个复杂度都跑不满。
对于 Dinic 算法的复杂度，有如下 (3) 种情况：
- 一般的网络图：(O(n^2m))
- 单位容量的图：(O(minsqrt{m},n^{frac{2}{3}})⋅m))
- 二分图：(O(msqrt{n}))
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int N=1e4+5,M=2e5+5;
int n,m,s,t,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];
void add(int u,int v,int w) {
ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
memset(dep,0,sizeof(dep));
memcpy(cnr,lnk,sizeof(lnk));
std::queue<int> q;
q.push(s),dep[s]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=lnk[u];i;i=nxt[i]) {
int v=ter[i];
if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
}
}
return dep[t];
}
int dfs(int u,int t,int flow) {
if(u==t) return flow;
int ans=0;
for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
cnr[u]=i;/******/
int v=ter[i];
if(val[i]&&dep[v]==dep[u]+1) {
int x=dfs(v,t,std::min(val[i],flow-ans));
if(x > 0) val[i]-=x,val[i^1]+=x,ans+=x; /***优化不能省***/
}
}
if(ans<flow) dep[u]=-1;/******/
return ans;
}
int dinic(int s,int t) {
int ans=0;
while(bfs(s,t)) {
int x;
if((x=dfs(s,t,1<<30))) ans+=x;
}
return ans;
}
int main() {
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
}
printf("%d
",dinic(s,t));
return 0;
}