本文共 4872 字，大约阅读时间需要 16 分钟。

网络流涉及到的概念好多 \(qwq\) ，梳理一下。

流网络

流网络是一个有向图，包含点集和边集。即 \(G=(V,E)\) 。
对于边 \(e:u\rightarrow v\) （也可以记为 \((u,v)\) ），有属性 \(c(u,v)\) ，称为容量。可以将其比喻为水管在单位时间可以流过的最大水量。

而图 \(G\) 中有两个特殊的点，称为源点和汇点，通常记为 \(s\) , \(t\) ，可以将源点比喻为无限的水源，将汇点比喻为能够容纳无穷的水的容器。

可行流

我们记 \(f(u,v)\) 为边 \(e:u\rightarrow v\) 当前的流量，流量需要满足两个约束：

1. 容量限制：即 \(0 \leq f(u,v) \leq c(u,v)\)
2. 流量守恒：除了源点、汇点，其他点流入的流量等于流出的流量，正式地说： \(\sum_{(u,x) \in E} f(u,x) = \sum_{(x,v)\in E)} f(x,v)\)

流量值

用单位时间流出源点的流量来刻画，记为 \(|f|=\sum_{(s,x) \in E} f(s,x) - \sum_{(y,s)\in E)}f(y,s)\) 。

最大流

又称为最大可行流，即对于 \(G\) 中可行流构成的集合中，流量值最大的元素。

残留网络

又称为残量网络，注意，残留网络总是针对原图 \(G=(V,E)\) 中的某一个可行流而言的，因此，可以残留网络看成是可行流的一个函数，通常记为 \(G_f\) 。

\(G_f=(V_f,E_f)\) ，其中 \(V_f=V\) ， \(E_f=E和E中所有的反向边\) 。

残留网络中的容量记为 \(c'(u,v)\) ，定义为：

增广路径

如果从源点 \(s\) 出发沿着残留网络中容量大于 \(0\) 的边走，可以走到汇点 \(t\) ，那么将走过的边所组成的路径称为增广路径。

原网络可行流+残留网络可行流也是原网络的一个可行流

正式地说， \(f+f'\) 属于 \(G\) 的一个可行流，且有 \(|f+f'|=|f|+|f'|\) 。

割

是网络中顶点的一个划分，把所有顶点划分成两个顶点集合 \(S\) 和 \(T\) ，其中源点 \(s\) 属于 \(S\) ，汇点 \(t\) 属于 \(T\) ，而且有 \(S \cup T=V\) ，\(S \cap T=\emptyset\) ，记为 \([S,T]\) 。

割的容量

\(c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)\)

最小割

\(G\) 中所有割组成的集合中，容量最小的元素。

割的流量

\(f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v) - \sum_{u\in T}\sum_{v\in S}f(u,v)\)

任意割的流量 \(\leq\) 容量

正式地说，即 \(\forall [S,T]\) ，\(f(S,T)\leq c(S,T)\) 。

证明：（待补充）

最大流最小割定理

1. \(f\) 是最大流
2. \(G_f\) 不存在增广路
3. \(\exists [S,T]\) ，满足 \(|f|=c(S,T)\)

最大流最小割定理指的是：上面的三个命题是等价的。（也就是说可以互推）。

证明：

• 先证明 1 可以推得 2 ：
  反证即可，如果 \(G_f\) 存在增广路，那么原图 \(G\) 中存在流量大于 \(0\) 的可行流 \(|f'|\) ，那么 \(f+f'\) 也是可行流，且流量为 \(|f|+|f'|>|f|\) ，矛盾。

• 下证 2 可以推得 3 ：
  我们将对于 \(G_f\) 中从 \(s\) 出发沿着容量大于 \(0\) 的边可以到达的点全部放入集合 \(S\) 中，然后令 \(T=V-S\) 。
  那么对于点 \(x \in S\) ，\(y \in T\) ，边 \((x,y)\) 一定有 \(f(x,y)=c(x,y)\) 。
  而对于点 \(x \in T\) ，\(y \in S\) 。必然有 \(f(x,y)=0\) 。因而割可以被构造出来。

• 最后证明 3 可以推得 1 ：
  因为 \(|f|\leq 最大流 \leq c(S,T)\) ，而由 3 可知 \(|f|=c(S,T)\) ，故上式取等，即有 \(f\) 是最大流。

最大流FF方法

基于这样的思路：

1. 寻找增广路
2. 利用增广路更新残留网络

一直这样做，直到找不到增广路，那么即可求得最大流。

算法：

单路增广：EK算法

#include<bits/stdc++.h>using namespace std;const int INF=1e9;const int N=1005, M=10010;int n, m, S, T;struct node{    int to, c, next;}e[M<<1];int h[N], tot;// 残量网络建图，初始时正向的容量是 c, 反向容量是 0 。void add(int u, int v, int cap){    e[tot].to=v, e[tot].c=cap, e[tot].next=h[u], h[u]=tot++;    e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;  }int d[N], pre[N]; // d[u] 表示 S 到点 u 路径容量的最小值， pre[u] 表示 u 的前驱边。bool vis[N];int q[N];// bfs 找增广路。bool bfs(){    memset(vis, false, sizeof vis);    int hh=0, tt=-1;    q[++tt]=S, vis[S]=true, d[S]=INF;    while(tt>=hh){        int hd=q[hh++];        for(int i=h[hd]; ~i; i=e[i].next){            int go=e[i].to;            if(vis[go] || !e[i].c) continue;            vis[go]=true, q[++tt]=go;            d[go]=min(d[hd], e[i].c);            pre[go]=i;            if(go==T) return true;        }    }    return false;}int EK(){    int res=0;    while(bfs()){        res+=d[T];        for(int i=T; i!=S; i=e[pre[i]^1].to){            e[pre[i]].c-=d[T], e[pre[i]^1].c+=d[T];        }    }    return res;}int main(){    memset(h, -1, sizeof h);    cin>>n>>m>>S>>T;    while(m--){        int u, v, cap; cin>>u>>v>>cap;        add(u, v, cap);    }       cout<<EK()<<endl;    return 0;}

多路增广：dinic算法
代码：

#include<bits/stdc++.h>using namespace std;#define gc() (st==ed&&(ed=(st=buf)+fread(buf,1,100000,stdin),st==ed)?EOF:*st++)char buf[100001],*st=buf,*ed=buf;void read(int &a){    a=0;char c=gc();    while(c>'9'||c<'0')c=gc();    while(c>='0'&&c<='9')a=a*10+c-48,c=gc();}const int INF=0x3f3f3f3f;const int N=10010, M=1e5+5;struct node{    int to, c, next;}e[M<<1];int h[N], tot;void add(int u, int v, int cap){    e[tot].to=v, e[tot].c=cap, e[tot].next=h[u], h[u]=tot++;    e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;  }int n, m, S, T;int d[N], q[N], cur[N];bool bfs(){    memset(d, -1, sizeof d);    int tt=-1, hh=0;    q[++tt]=S, d[S]=0, cur[S]=h[S];    while(tt>=hh){        int hd=q[hh++];        for(int i=h[hd]; ~i; i=e[i].next){            int go=e[i].to;            if(d[go]==-1 && e[i].c){                d[go]=d[hd]+1;                cur[go]=h[go];                if(go==T) return true;                q[++tt]=go;            }        }    }    return false;}int find(int u, int limit){    if(u==T) return limit;    int flow=0;    for(int i=cur[u]; ~i && flow<limit; i=e[i].next){        cur[u]=i;        int go=e[i].to;        if(d[go]==d[u]+1 && e[i].c){            int t=find(go, min(e[i].c, limit-flow));            if(!t) d[go]=-1;            e[i].c-=t, e[i^1].c+=t, flow+=t;        }    }    return flow;}int dinic(){    int res=0, flow;    while(bfs()) while(flow=find(S, INF)) res+=flow;    return res;}int main(){    memset(h, -1, sizeof h);    read(n), read(m), read(S), read(T);    while(m--){        int u, v, cap; read(u), read(v), read(cap);        add(u, v, cap);    }    cout<<dinic()<<endl;    return 0;}