题意
给出一个网络，求流量的最大值
sol
网络流板子题。
网络流是 OI 中比较常用的算法之一，以较高的建图难度深受出题人喜爱，不过近几年题目数量减少。
当然，在学习建图之前，需要先学会网络流的板子。
一些定义
（部分摘自 OI-Wiki）
网络是特殊的有向图 \(G=(V,E)\)；
源点 \(s\) 是网络的起点，汇点 \(t\) 是网络的终点，\(s,t \in V\)；
对于\(\forall (u,v) \in E\)，其容量为 \(c(u,v)\)，特别的，若 \((u,v) \notin E\)，\(c(u,v) = 0\)
对于\(\forall (u,v) \in E\)，其流量为 \(f(u,v)\)，且满足以下性质：
- \(\forall (u,v) \in E, 0\le f(u,v) \le c(u,v)\)
- \(\forall u \in V - \{s,t\}, \sum_{x\in V} f(u,x) = \sum_{x\in V} f(x,u)\)
对于一个网络上的一个流，我们定义其流量 \(|f|=\sum_{x\in V} f(s,x) - \sum_{x\in V} f(x,s)\)
对于一个网络 \(G\)，若 \(S\cap T=V\) 且 \(S\cup T=\varnothing\) 且 \(s \in S,t \in T\)，则 {S,T} 是 \(G\) 的一个割，其容量 \(||S,T||=\sum_{u\in S}\sum_{v\in T} c(u,v)\)
对于网络 \(G\)，其可能的最大的流量 \(f\) 即为 \(G\) 的最大流
Edmond-Karp
在残量网络中 BFS 找到一条增广路（从源点到汇点容量为正的路径），累加流量，最后更新残量网络。
理论复杂度上限 \(O(nm^2)\)，实际可处理 \(10^3 \sim 10^4\) 的数据
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef unsigned int UI;
typedef long long LL;
constexpr int N = 205, M = 10005;
constexpr UI INF = 1 << 31;
int h[N], e[M], f[M], ne[M], idx;
int pre[N];
UI d[N];
bool st[N];
int n, m, S, T;
void add(int a, int b, int c){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}
bool BFS(){
memset(st, false, sizeof st);
queue<int> q;
st[S] = true, d[S] = INF;
q.push(S);
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (!st[j] && f[i]) {
st[j] = true;
pre[j] = i;
d[j] = min(d[t], (UI) f[i]);
if (j == T) return true;
q.push(j);
}
}
}
return false;
}
LL EK(){
LL res = 0;
while (BFS()) {
res += d[T];
for (int u = T; u != S; u = e[pre[u] ^ 1])
f[pre[u]] -= d[T], f[pre[u] ^ 1] += d[T];
}
return res;
}
int main(){
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(h, -1, sizeof h);
while (m -- ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%lld\n", EK());
return 0;
}
Dinic
在残量网络中进行分层（防止出现环），然后爆搜每一条增广路，如果可行的话就累加
注意一部分优化：
- 在爆搜的过程中，如果发现当前节点的流出流量已经超过流入流量，则直接返回
- 在爆搜的过程中，如果发现某个节点无法提供任何流量，那么就在这个残量网络中删除这个节点
- 在爆搜的过程中，如果重复遍历某个点，那么继续上一次未搜索完的弧遍历（当前弧优化）
理论复杂度上限 \(O(n^2m)\)，实际可处理 \(10^4 \sim 10^5\) 的数据。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef unsigned int UI;
const int N = 1205, M = 240005;
const UI INF = 1 << 31;
int h[N], e[M], ne[M], idx;
UI f[M];
int d[N], cur[N];
int n, m, S, T;
void add(int a, int b, int c){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}
bool bfs(){
memset(d, -1, sizeof d);
queue<int> q;
q.push(S), d[S] = 0, cur[S] = h[S];
while (!q.empty()) {
int t = q.front(); q.pop();
for (int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (d[j] == -1 && f[i]) {
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q.push(j);
}
}
}
return false;
}
UI find(int u, UI limit) {
if (u == T) return limit;
UI flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]){ // 优化 1
cur[u] = i; // 优化 3
int j = e[i];
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(limit - flow, f[i]));
if (!t) d[j] = -1; // 优化 2
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic(){
int res = 0, flow;
while (bfs()) while (flow = find(S, INF)) res += flow;
return res;
}
int main(){
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(h, -1, sizeof h);
while (m -- ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", dinic());
}
Dinic 算法在大部分题目中都够用，因为卡 Dinic 是没有浮木的行为。
此外还有效率差不多的 ISAP 算法和相对更快的 HLPP 算法（理论上届复杂度 \(O(n^2\sqrt{m})\)），但是不会。