## 概念 好多好多具体定义请看 [网络流简介 - OI Wiki](https://oi-wiki.org/graph/flow/) 和 [最大流 - OI Wiki](https://oi-wiki.org/graph/flow/max-flow/) ## EK 算法 简单来说就是每次 BFS 找到一条增广路，注意一下流量合不合法就可以了。 然后我们把这条路走一边，最大流量减一减，然后给答案加上最小流量就可以了。 这样其实也有问题，不一定找到最优解，我们可以使用**反悔边**，增广的时候要注意建造反向边，这样子程序可以进行反悔。假如我们对这条路进行增广了，那么其中的每一条边的反向边的流量就是它的流量。 这样，我们把边从 $2$ 开始编号，每条边 $i$ 的反悔边为 $i \oplus1$。 ### 时间复杂度 $O(nm^2)$，实际上远远达不到，一般能跑 $10^3\text{~}10^4$ 的数据。 [模板题](https://www.luogu.com.cn/problem/P3376) ### 代码 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=220, M=1e4+10; int n, m, s, t, incf[N], pre[N], v[N], maxflow; int tot=1, to[M], val[M], nxt[M], head[N]; void add(int x, int y, int z) { to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot; } bool bfs() { memset(v, 0, sizeof v); queue<int> q; q.push(s); v[s]=1; incf[s]=2e9; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (v[y] || !val[i]) continue; incf[y]=min(incf[x], val[i]); pre[y]=i; q.push(y); v[y]=1; if (y==t) return 1; } } return 0; } void update() { int x=t; while (x!=s) { int i=pre[x]; val[i]-=incf[t]; val[i^1]+=incf[t]; x=to[i^1]; } maxflow+=incf[t]; } signed main() { n=read(), m=read(), s=read(), t=read(); for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); add(x, y, z); add(y, x, 0); } while (bfs()) update(); printf("%lld\n", maxflow); return 0; } ``` ### Dinic 算法 EK 一次只找一条增广路，浪费时间，Dinic 一次可以找多条 #### 算法流程 1. 通过 bfs 构造分层图，直到汇点 2. 从源点开始 dfs ，每次只走比当前层数大 $1$ 的点，找到增广路并增广 #### 优化 1. 做 bfs 的时候，如果已经到达汇点，直接 `return 1;` 2. 做 dfs 的时候，每次只往层数大 $1$ 的地方流，如果一个点流不下去，标记深度为 $0$，以后就不会再做。 3. 如果当前剩余流量为 $0$，直接 `break` 4. 当前弧优化，即每张分层图上做过的边不会再做 原先是从 `head[x]` 开始做，现在没做一次 `head[x]` 就指向下一个节点，用另一个数组备份即可。 #### 注意 1. 加了当前弧优化后，最好在一个分层图中进行多次增广 2. 一定不能写这样的代码： ```cpp for (int &i=cur[x]; i && rest; i=nxt[i]) { ...... } ``` 要改成这样： ```cpp for (int &i=cur[x]; i; i=nxt[i]) { ...... if (rest==0) break; } ``` 这是因为第一种是先`i=nxt[i]`，再判断是否有剩余容量，直接跳过了一个点，就会多做很多次，时间大大增加！ ### 时间复杂度 增广层数一定增大，最多增广 $n-1$ 次 最坏时间复杂度为 $O(n^2m)$ 实际很小，一般可以处理 $10^4\text{~}10^5$的数据 ### 代码 ```cpp #include <cstdio> #include <cctype> #include <queue> #include <algorithm> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=210, M=1e4+10; int n, m, s, t, d[N], tot=1, head[N], cur[N], to[M], val[M], nxt[M]; bool bfs() { for (int i=1; i<=n; i++) cur[i]=head[i], d[i]=0; queue<int> q; q.push(s), d[s]=1; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (d[y] || !val[i]) continue; d[y]=d[x]+1; q.push(y); if (y==t) return 1; } } return 0; } int dinic(int x, int flow) { if (x==t) return flow; int rest=flow; for (int &i=cur[x]; i; i=nxt[i]) { int y=to[i]; if (d[y]!=d[x]+1 || !val[i]) continue; int k=dinic(y, min(rest, val[i])); if (!k) d[y]=0; val[i]-=k; val[i^1]+=k; rest-=k; if (!rest) break; } return flow-rest; } void add(int x, int y, int z) { to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot; } signed main() { n=read(), m=read(), s=read(), t=read(); for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); add(x, y, z); add(y, x, 0); } int maxflow=0, flow; while (bfs()) while (flow=dinic(s, 1e15)) maxflow+=flow; printf("%lld\n", maxflow); return 0; } ``` ### Dinic 二分图匹配 从源点向二分图一边的点连边，从另一边的点向汇点连边，两部分之间也连边，边权为 $1$ ，跑 Dinic 即可求出二分图最大匹配 时间复杂度： $O(m\sqrt{n})$，最多增广 $\sqrt n$ 次，具体证明我不会！可以参考 [OI-Wiki](https://oi-wiki.org/graph/flow/max-flow/#dinic)！ ## 参考 - [最大流 - OI Wiki](https://oi-wiki.org/graph/flow/max-flow/) - 《算法竞赛进阶指南》 Loading... ## 概念 好多好多具体定义请看 [网络流简介 - OI Wiki](https://oi-wiki.org/graph/flow/) 和 [最大流 - OI Wiki](https://oi-wiki.org/graph/flow/max-flow/) ## EK 算法 简单来说就是每次 BFS 找到一条增广路，注意一下流量合不合法就可以了。 然后我们把这条路走一边，最大流量减一减，然后给答案加上最小流量就可以了。 这样其实也有问题，不一定找到最优解，我们可以使用**反悔边**，增广的时候要注意建造反向边，这样子程序可以进行反悔。假如我们对这条路进行增广了，那么其中的每一条边的反向边的流量就是它的流量。 这样，我们把边从 $2$ 开始编号，每条边 $i$ 的反悔边为 $i \oplus1$。 ### 时间复杂度 $O(nm^2)$，实际上远远达不到，一般能跑 $10^3\text{~}10^4$ 的数据。 [模板题](https://www.luogu.com.cn/problem/P3376) ### 代码 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=220, M=1e4+10; int n, m, s, t, incf[N], pre[N], v[N], maxflow; int tot=1, to[M], val[M], nxt[M], head[N]; void add(int x, int y, int z) { to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot; } bool bfs() { memset(v, 0, sizeof v); queue<int> q; q.push(s); v[s]=1; incf[s]=2e9; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (v[y] || !val[i]) continue; incf[y]=min(incf[x], val[i]); pre[y]=i; q.push(y); v[y]=1; if (y==t) return 1; } } return 0; } void update() { int x=t; while (x!=s) { int i=pre[x]; val[i]-=incf[t]; val[i^1]+=incf[t]; x=to[i^1]; } maxflow+=incf[t]; } signed main() { n=read(), m=read(), s=read(), t=read(); for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); add(x, y, z); add(y, x, 0); } while (bfs()) update(); printf("%lld\n", maxflow); return 0; } ``` ### Dinic 算法 EK 一次只找一条增广路，浪费时间，Dinic 一次可以找多条 #### 算法流程 1. 通过 bfs 构造分层图，直到汇点 2. 从源点开始 dfs ，每次只走比当前层数大 $1$ 的点，找到增广路并增广 #### 优化 1. 做 bfs 的时候，如果已经到达汇点，直接 `return 1;` 2. 做 dfs 的时候，每次只往层数大 $1$ 的地方流，如果一个点流不下去，标记深度为 $0$，以后就不会再做。 3. 如果当前剩余流量为 $0$，直接 `break` 4. 当前弧优化，即每张分层图上做过的边不会再做 原先是从 `head[x]` 开始做，现在没做一次 `head[x]` 就指向下一个节点，用另一个数组备份即可。 #### 注意 1. 加了当前弧优化后，最好在一个分层图中进行多次增广 2. 一定不能写这样的代码： ```cpp for (int &i=cur[x]; i && rest; i=nxt[i]) { ...... } ``` 要改成这样： ```cpp for (int &i=cur[x]; i; i=nxt[i]) { ...... if (rest==0) break; } ``` 这是因为第一种是先`i=nxt[i]`，再判断是否有剩余容量，直接跳过了一个点，就会多做很多次，时间大大增加！ ### 时间复杂度 增广层数一定增大，最多增广 $n-1$ 次 最坏时间复杂度为 $O(n^2m)$ 实际很小，一般可以处理 $10^4\text{~}10^5$的数据 ### 代码 ```cpp #include <cstdio> #include <cctype> #include <queue> #include <algorithm> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=210, M=1e4+10; int n, m, s, t, d[N], tot=1, head[N], cur[N], to[M], val[M], nxt[M]; bool bfs() { for (int i=1; i<=n; i++) cur[i]=head[i], d[i]=0; queue<int> q; q.push(s), d[s]=1; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (d[y] || !val[i]) continue; d[y]=d[x]+1; q.push(y); if (y==t) return 1; } } return 0; } int dinic(int x, int flow) { if (x==t) return flow; int rest=flow; for (int &i=cur[x]; i; i=nxt[i]) { int y=to[i]; if (d[y]!=d[x]+1 || !val[i]) continue; int k=dinic(y, min(rest, val[i])); if (!k) d[y]=0; val[i]-=k; val[i^1]+=k; rest-=k; if (!rest) break; } return flow-rest; } void add(int x, int y, int z) { to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot; } signed main() { n=read(), m=read(), s=read(), t=read(); for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); add(x, y, z); add(y, x, 0); } int maxflow=0, flow; while (bfs()) while (flow=dinic(s, 1e15)) maxflow+=flow; printf("%lld\n", maxflow); return 0; } ``` ### Dinic 二分图匹配 从源点向二分图一边的点连边，从另一边的点向汇点连边，两部分之间也连边，边权为 $1$ ，跑 Dinic 即可求出二分图最大匹配 时间复杂度： $O(m\sqrt{n})$，最多增广 $\sqrt n$ 次，具体证明我不会！可以参考 [OI-Wiki](https://oi-wiki.org/graph/flow/max-flow/#dinic)！ ## 参考 - [最大流 - OI Wiki](https://oi-wiki.org/graph/flow/max-flow/) - 《算法竞赛进阶指南》 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏