小 W 带你速通网络流全家桶
wsy_I
·
·
算法·理论
0x0 开头
::::success[结算画面]
::::
让我们，开始通关网络流全家桶吧！
由于本文是速通，所以有一些题目并不是使用最规范的写法，而是使用一些奇奇怪怪的做法来快速通过。并且，大部分地方只讲方法不谈证明。
前置知识：图的遍历（bfs, dfs），最短路。
0x1 【模板】网络最大流
link
其实最大流这个东西概念很好理解，就这一句话：
源点看做自来水厂，汇点看做你的家，边看做水管，求在不炸水管的情况下让自来水厂输给你家的水量最大，求这个最大水量。
那我们就可以想出来一些做法了。有一个很显然的做法就是贪心：从源点向汇点做 bfs，找一条源点到汇点的路径，其中没有一条边边权非 0，让这一条路径的流量都减去最小值，并且将最大流加上这个最小值。之后将这个操作简称“满流”。一直执行到源点到汇点不存在最小边权非 0 的路径为止。我们以后将这种路径称为“增广路”。
令人悲伤的是，这个贪心是错的。我们考虑下面这个图：
那么，我们就要拿出正经的最大流算法来了。最大流算法进行了一个精妙的操作：退流。具体是这样的：由于我们一条边流过了一些流量之后，这个流法可能不是最优的，所以我们需要一个“反悔”的方法，具体表现为加反向边，表示这条边流过的流量。
例如上面的图，现在就长这样了：
每次找到一条增广路，满流的时候，我们在反向边也相应的**加上**流量，表示从这条边以后可以“退回”这个流量。例如上面的图，假如我们走了 $1\to 3\to 2\to 4$ 这一条错误的增广路之后，就变成了这样：
容易发现，现在还存在一条 $1\to 2\to 3\to 4$ 的增广路，于是我们对于这一条增广路满流，可以得到下面的图：
现在最大流是正确的 $2$ 了！我们来感性理解一下退流这个操作，主要的依据就是增广 $1\to 3\to 2\to 4$ 和 $1\to 2\to 3\to 4$ 和增广 $1\to 2\to 4$ 和增广 $1\to 3\to 4$ 这两种增广方案是一样的，由于中间的 $2\to 3$ 这一条边的流量先被流了过去，又被退了回来。退回来原本不优的流就是退流操作保证能够得到最优的最大流的基础。
接下来，我们来考虑如何找这一条增广路。显然，有两种方法：dfs 和 bfs。
假如我们使用 dfs 去找增广路，那么就会出现一个问题：这个算法的速度很依赖每一个节点邻接节点存储的顺序。比如对于上面的图，我们将 $1\to 2,2\to 4,1\to 3,3\to 4$ 这四条边的流量变为 $10^9$，但是我们的算法因为存储顺序可能会在 $1\to 3\to 2\to 4$ 和 $1\to 2\to 3\to 4$ 这两条增广路中反复推流，每一次最大流只增长 $1$，最后需要增广 $2\times10^9$ 次，显然非常慢。
因此我们考虑 bfs，这样我们找到的增广路都是比较短的，就可以去除一些在流量很小的长路上反复推流的情况，使得算法跑的更快。实际上，可以证明找到的增广路数量不会超过 $O(nm)$ 条，因此总时间复杂度 $O(nm^2)$。这个就是最大流的 Edmonds-Karp 算法。代码实现如下：
::::success[code]
[评测记录](https://www.luogu.com.cn/record/258752737)
```cpp
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e2 + 10;
const int M = 1e4 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, s, t;
struct node { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {//链前存图
e[++ tot] = {v, w, head[u]};
head[u] = tot;
}
bool vis[N];
int incf[N], pre[N], mf;//incf：到这个点可以允许的最大流量，pre：在增广路上这个点的前驱节点
queue<int> q;
bool bfs() {//bfs找增广路
while(!q.empty()) q.pop();
memset(vis, false, sizeof vis);
q.push(s);
vis[s] = true;
incf[s] = INF;//源点初始可以流出无限的流量，所以这里是 INF
while(!q.empty()) {
int f = q.front();
q.pop();
for(int i = head[f]; i != -1; i = e[i].nex) {
if(e[i].w) {//这条边的边权非 0 才能走
int v = e[i].to;
if(vis[v]) continue;
vis[v] = true;
incf[v] = min(e[i].w, incf[f]);//计算最大流量
pre[v] = i;//记录前驱节点
q.push(v);
if(v == t) return true;//找到汇点了
}
}
}
return false;//走不到汇点，说明不存在增广路了
}
void EK() {
while(bfs()) {//一直找增广路直到没有
int u = t;
while(u != s) {//满流这条增广路
int i = pre[u];
e[i].w -= incf[t];
e[i ^ 1].w += incf[t];//记住，这里一定是增流，不要写成 -= incf[t]！！！
u = e[i ^ 1].to;
}
mf += incf[t];//累加最大流
}
}
signed main() {
memset(head, -1, sizeof head);
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
adde(u, v, w);//正向边
adde(v, u, 0);//反向边
}
EK();
cout << mf << endl;
return 0;
}
```
::::
~~这道题我们已经 AC 了！下一题！~~
但是 $O(nm^2)$ 的复杂度太差了，甚至在模板题这种数据规模并不大的题目都能跑 $300$ 毫秒以上，在一些题目中显然会被卡爆。因此，我们需要更快的最大流算法！
我们来尝试考虑 Edmonds-Karp 算法有哪些低效的地方。由于这个算法每次只找一条增广路，所以比较低效，我们可以尝试一次找多条增广路。
但是 bfs 也有其局限性，也就是一个节点最多记录一个前驱，不然会有各种奇奇怪怪的实现问题。因此，我们重新考虑之前被抛弃了的 dfs。
dfs 自身就可以访问一个节点很多次，所以 dfs 是天然适配一次找多条增广路，即“多路增广”的。然而 dfs 的反复推流我们并不希望看到，所以我们还要使用 bfs 来先做一遍“分层”，即求出每一个节点到源点的最短距离。然后使用 dfs 找增广路的时候，这个节点访问下一个节点还必须要下一个节点到源点的距离是这个节点到源点的距离加 $1$。这样就可以很好让 dfs 兼具 bfs 的性质，每一次找到最短的增广路，避免 dfs 的反复推流啦~
接着考虑怎么实现。从这个节点开始，依次访问所有满足条件的邻接节点，看看每一个邻接节点到汇点能流多少流量，把源点到这个点流的流量减去。如果源点到这个点的流量已经流完了，我们就退出访问，相当于一个小剪枝。代码实现如下：
::::success[code]
[提交记录](https://www.luogu.com.cn/record/258819616)
```cpp
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e2 + 10;
const int M = 1e4 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, s, t;
struct node { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {
e[++ tot] = {v, w, head[u]};
head[u] = tot;
}
int mf, dep[N];
queue<int> q;
bool bfs(int s) {//bfs 分层
memset(dep, 0, sizeof dep);
q.push(s);
dep[s] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(!dep[v] && e[i].w) {//记住这里的 e[i].w，不要漏了，剩余流量为 0 的边不能走
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t] != 0;//如果 dep[t] = 0，表明走不到 t，即不存在增广路
}
int dfs(int u, int flow) {//dfs 增广，来到 u 点可以流 flow 的流量
if(u == t) return flow;//如果到了汇点直接把流量返回
int delta = flow;//这个点的剩余流量
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(dep[v] == dep[u] + 1 && e[i].w) {//同样不要忘了 e[i].w
int f = dfs(v, min(delta, e[i].w));//访问这个点，求出可以流的流量
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;//再强调一次一定不要写成 -=！！！
if(delta == 0) break;//如果没有流量可流了就退出
}
}
return flow - delta;//这个点流出的流量就是可以流的流量减去剩下的流量
}
void dinic() {
while(bfs(s)) {//同样一直分层，直到没有增广路
mf += dfs(s, INF);//累加最大流
}
}
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
adde(u, v, w);
adde(v, u, 0);
}
dinic();
cout << mf << endl;
return 0;
}
```
::::
此时的你：小 W 你骗我！！！这完全是劣化！！！还 TLE 了！！！
别急，这种做法之所以还没有发挥出它全部的威力，是因为它少了一个优化：当前弧优化。
当前弧优化基于这么一个会让算法变慢的点：一个点会被访问多次，由于这个点可能会有多个前驱节点。然后，多个前驱节点访问这个节点，这个节点就会访问很多遍它的邻接点，即使这些邻接点根本流不了一点流量了。
因此，我们可以记录一下这个点那些邻接点已经被榨干了，到汇点流不出一点流量了。由于我们的邻接点是按照顺序遍历的，我们就只需要记录每个店当前遍历到的邻接点，下一次访问这个节点的时候从这个当前遍历到的邻接点开始遍历就行了。这个当前遍历到的邻接点就被叫做“当前弧”。
这个就是完整的 dinic 算法。dinic 的时间复杂度是 $O(n^2m)$，实际上根本跑不满，对于大部分图跑的飞快，随机图上跑 $n=4\times 10^4$ 完全不带压力。代码实现和之前的不带当前弧优化的版本基本没什么区别：
::::success[code]
[评测记录](https://www.luogu.com.cn/record/264962191)
```cpp
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
using namespace std;
const int N = 500 + 10;
const int M = 10000 + 10;
const int INF = 0x3f3f3f3f;
int n, m, u[M], v[M], w[M], s, t;
struct node { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {
e[++ tot] = {v, w, head[u]};
head[u] = tot;
e[++ tot] = {u, 0, head[v]};
head[v] = tot;
}
int dis[N], cur[N];//cur：每个点的当前弧
queue<int> q;
bool bfs(int s, int t) {
memset(dis, 0, sizeof dis);
q.push(s);
dis[s] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(!dis[v] && e[i].w) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t] != 0;
}
int dfs(int u, int flow, int t) {
if(u == t) return flow;
int delta = flow;
for(int& i = cur[u]; i != -1; i = e[i].nex) {//使用引用来让 cur[u] 随着 i 一直更新，一种很简洁优雅的写法
int v = e[i].to;
if(dis[v] == dis[u] + 1 && e[i].w) {
int f = dfs(v, min(delta, e[i].w), t);
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if(delta == 0) break;
}
}
return flow - delta;
}
int dinic(int s, int t) {
int mf = 0;
while(bfs(s, t)) {
memcpy(cur, head, sizeof head);//cur 的初始值为 head 数组
mf += dfs(s, INF, t);
}
return mf;
}
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> w[i];
adde(u[i], v[i], w[i]);
}
cout << dinic(s, t) << endl;
return 0;
}
```
::::
# 0x2 【模板】最大流 加强版/预流推进
[link](https://www.luogu.com.cn/problem/P4722)
一看这道题，最大流模板啊，和之前的题目一样，然后直接把之前的 dinic 交了上去。
恭喜你获得了 $16$ 分的高分！很明显，这道题想要强迫你写 HLPP。
然而再学一个算法实在是太浪费时间了，所以我们考虑魔改 dinic 使其通过此题。
我们首先考虑 dinic 慢的根本原因在哪里。其实原因就是在最短的增广路中可能有一些边的流量很小，我们满流这条路的时候对于最大流的贡献并不大，而这样却浪费了我们宝贵的时间。所以我们可以把边分批次加进去，每次加进去之后就跑一次最大流，之后再从跑完之后剩下的图中添加这些边。这样就可以排除大部分增广路流量很小的情况。
经过了这个优化了之后，dinic 就基本上卡不掉了，虽然这道题还是需要精细实现才能通过。精细实现具体包括下面几点：
- 把重边压到一起，具体是使用一个二维数组统计每一对点对 $(u, v)$ 之间的流量，记作 $w_{u, v}$。对于每一个点对，如果 $(u, v)$ 或者 $(v, u)$ 的流量不为 $0$，就添加两条边：$(u, v, w_{u, v})$ 和 $(v, u, w_{v, u})$。为什么只要一边不为 $0$ 就要都加上？这是因为我们需要反向边来退流。
- 采用精细的加边阈值。一个不错的选择是按照每一次 $4$ 位划分，一共跑 $8$ 次最大流。
然后我们就可以卡过去了！只不过如果你之前的 dinic 哪里常数有点大，可能还是过不去，可以参考我的代码来优化：
::::success[code]
[评测记录](https://www.luogu.com.cn/record/259168953)
```cpp
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1200 + 10;
const int M = 240000 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, s, t, mp[N][N];
struct node { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {
e[++ tot] = {v, w, head[u]};
head[u] = tot;
}
int mf, dep[N];
queue<int> q;
bool bfs(int s) {
memset(dep, 0, sizeof dep);
while(!q.empty()) q.pop();
q.push(s);
dep[s] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(!dep[v] && e[i].w) {
dep[v] = dep[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return dep[t] != 0;
}
int cur[N];
int dfs(int u, int flow) {
if(u == t) return flow;
int delta = flow;
for(int& i = cur[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(dep[v] == dep[u] + 1 && e[i].w) {
int f = dfs(v, min(delta, e[i].w));
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if(delta == 0) break;
}
}
return flow - delta;
}
void dinic() {
mf = 0;
while(bfs(s)) {
memcpy(cur, head, sizeof head);
mf += dfs(s, INF);
}
}
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
mp[u][v] += w;//把重边压到一起
}
int ans = 0;
for(int b = 28; b >= 0; b -= 4) {//按 4 位划分
for(int u = 1; u <= n; u++) {
for(int v = u + 1; v <= n; v++) {
if((mp[u][v] > 0 || mp[v][u] > 0) &&
(mp[u][v] >= (1 << b) || mp[v][u] >= (1 << b))) {
adde(u, v, mp[u][v]);//添加双向边
adde(v, u, mp[v][u]);
mp[u][v] = 0;//清除这条边，避免以后加上去第二遍
mp[v][u] = 0;
}
}
}
dinic();
ans += mf;
}
cout << ans << endl;
return 0;
}
```
::::
# 0x3 【模板】最小费用最大流
[link](https://www.luogu.com.cn/problem/P3381)
最小费用最大流，在题目中的定义非常抽象，其实题目搞的有一点复杂了，大概说来是这样的：
> 自来水厂又要到你家输水，这一次情况变得复杂了一些。自来水厂到你家还是有一些管道，但是这一次管道并没有真正的建出来，而是需要一定成本建造，其中每一个管道有一个费用 $c$，表示在这里建造最大流量为 $f$ 的管道需要 $f\times c$ 的费用。同样的，由于地形限制，建造的管道也有流量上界。自来水厂想要在保证你家可以输到可能的最大水量的情况下保证建造成本最小，你需要求出这个最大水量和最小成本。
还是一个网络流问题啊。那么我们就可以想想，该怎么改最大流算法来让它同时支持最小费用？有一个朴素的想法是每一次找增广路的时候，同时让这一条增广路的费用总和最小。这个朴素的想法实际上是对的。
然而这个朴素的想法似乎是基于 Edmonds-Karp 的，这显然并不优秀，所以我们要考虑该如何改一下这个想法来让它支持 dinic。
把 dinic 的 dfs 分层改成最短路即可。这里的最短路要选用 spfa，尽管它已经死了，因为会有负权边。（由于退流会减少费用，所以反向边的费用要设成负的）然后 dfs 遍历邻接点的时候也用是否在最短路上来判断就可以了。具体细节会在代码中说明。记得还要使用一个 $vis$ 数组来标记每一个点是否在当前增广路上，因为可能会存在环，使用费用意义上的最短路无法避免一直在环里打转。
::::success[code]
[评测记录](https://www.luogu.com.cn/record/259006548)
```cpp
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 5e3 + 10;
const int M = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, s, t;
struct edge { int to, w, c, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w, int c) {
e[++ tot] = {v, w, c, head[u]};
head[u] = tot;
e[++ tot] = {u, 0, -c, head[v]};
head[v] = tot;
}
int dis[N];
bool inq[N];
queue<int> q;
bool spfa(int s) {//将 bfs 换为 spfa，就是标准的 spfa 模板，没什么好说的。
for(int i = 1; i <= n; i++) dis[i] = INF;
dis[s] = 0;
q.push(s);
inq[s] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(e[i].w && dis[v] > dis[u] + e[i].c) {
dis[v] = dis[u] + e[i].c;
if(!inq[v]) {
q.push(v);
inq[v] = true;
}
}
}
}
return dis[t] != INF;
}
int cur[N];
bool vis[N];
int dfs(int u, int flow) {
if(u == t) return flow;
int delta = flow;
vis[u] = true;//标记节点为已访问
for(int i = cur[u]; i != -1; i = e[i].nex) {
cur[u] = i;
int v = e[i].to;
if(!vis[v] && dis[v] == dis[u] + e[i].c && e[i].w) {//三个条件：当前增广路未访问，在最短路上，流量不为 0
int f = dfs(v, min(delta, e[i].w));
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if(delta == 0) break;
}
}
vis[u] = false;//这一句千万不要漏了，不然这一个节点无法重复访问，多路增广也就用不了了
return flow - delta;
}
int mflow, mcost;
void dinic() {
while(spfa(s)) {
memcpy(cur, head, sizeof head);
int f = dfs(s, INF);
mflow += f;
mcost += dis[t] * f;//由于我们严格限制了流到汇点的距离都等于最短路，所以 dis[t] 也就是流量所流过的费用，直接累加即可
}
}
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++) {
int u, v, w, c;
cin >> u >> v >> w >> c;
adde(u, v, w, c);
}
dinic();
cout << mflow << " " << mcost << endl;
return 0;
}
```
::::
# 0x4，0x5，0x6 上下界网络流三兄弟
[link1](https://www.luogu.com.cn/problem/P14578)，[link2](https://www.luogu.com.cn/problem/P14579)，
[link3](https://www.luogu.com.cn/problem/P14580
~~大部分是从自己题解里抄的~~
## 1. 无源汇上下界可行流
先把样例 $1$ （我自己做了一点改动）拿过来吧。
我们如何判断这个图中，是否存在可行流？其实这个并不困难，我们来一步步分析。
由于这个图中，每一条边的流量有下界，也就是边至少流这么多的流量，所以我们考虑把这些流量先流过去。这一条边剩下的流量就是这一条边的上界减去下界，即 $r_i - l_i$。
现在这个图就变成这样了（其中蓝色表示已经流过的流量，红色表示还可以流的流量）：
容易发现，现在这不是一个可行流，因为有一些点的流入和流出不是平衡的。流入和流出的平衡性如下图所示（绿色表示流入大于流出，黄色表示流出大于流入，暗红色表示这个节点的流入减流出）：
如果能够形成可行流，那么所有节点的流入应该等于流出，也就是不存在供需不平衡的情况。也就是，我们需要用剩下的流量去“补齐”这些不平衡的点。
那该怎么“补齐”呢？这个时候就需要请出我们的最大流了。建立超级源点和超级汇点，超级源点向每一个绿色的点连边，每一个黄色的点向超级汇点连边，边权为这个点流量不平衡的绝对值。于是这个图就变成了这样：
然后跑出 $S\to T$ 的最大流，如果与 $T$ 相连的所有边都满流，那么有可行流，否则没有。
为什么？因为最大流表示着从源点到汇点最多可以“补齐”的流量，也就是从绿色的点最多能过补到黄色的点的流量，如果与 $T$ 相连的所有边都满流，就标志着每一个供需不平衡的点都可以被补齐。比如上面的图，最大流跑出来是这样的：
令人悲伤的是，由于 $3\to T$ 这一条边没有满流，所以这个图不能形成一个可行流。
::::success[code]
[评测记录](https://www.luogu.com.cn/record/259084507)
```cpp
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
const int M = 3e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m, u[M], v[M], l[M], r[M], bal[N], s, t, ef, id[M];
struct edge { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {
e[++ tot] = {v, w, head[u]};
head[u] = tot;
e[++ tot] = {u, 0, head[v]};
head[v] = tot;
}
int dis[N];
queue<int> q;
bool bfs(int s) {
memset(dis, 0, sizeof dis);
dis[s] = 1;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(e[i].w && !dis[v]) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t] != 0;
}
int cur[N];
int dfs(int u, int flow) {
if(u == t) return flow;
int delta = flow;
for(int i = cur[u]; i != -1; i = e[i].nex) {
cur[u] = i;
int v = e[i].to;
if(dis[v] == dis[u] + 1 && e[i].w) {
int f = dfs(v, min(delta, e[i].w));
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if(delta == 0) break;
}
}
return flow - delta;
}
int mf = 0;
void dinic() {
while(bfs(s)) {
memcpy(cur, head, sizeof cur);
mf += dfs(s, INF);
}
}
int main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> l[i] >> r[i];
adde(u[i], v[i], r[i] - l[i]);
bal[v[i]] += l[i];//统计流量是否平衡
bal[u[i]] -= l[i];
id[i] = tot;
}
s = n + 1;
t = n + 2;
for(int i = 1; i <= n; i++) {
if(bal[i] > 0) {
adde(s, i, bal[i]);//大于0，源点向该点连边
ef += bal[i];
}
if(bal[i] < 0) adde(i, t, -bal[i]);//小于9，该点向汇点连边
}
dinic();
if(mf < ef) cout << "No\n";//没法让汇点的所有边满流，不存在可行流
else {
cout << "Yes\n";//否则存在
for(int i = 1; i <= m; i++) cout << l[i] + e[id[i]].w << endl;//流量就是下界加上第二次最大流跑出来的调节流量
}
return 0;
}
```
::::
## 2. 无源汇转有源汇
这一步其实非常简单，我们只需要在原本的源点和汇点之间建一条下界为 $0$，上界为 $\infin$ 的边就可以了。为什么呢？因为在网络流中，我们可以向源点灌无限多的水，汇点是一个无底洞，可以接受无限多的水。加了这一条边权为 $\infin$ 的边以后，我们向源点就可以最大有 $\infin$ 的流量，汇点也可以最大流出 $\infin$ 的流量，这就契合了源汇的定义。
比如样例，现在就是这样的：
我们还是跑出 $S\to T$ 的最大流，那就是这样的了（注意到由于有那一条新添加的边，所以我们可以通过走 $S\to 4\to 5\to 1\to T$ 来得到满流了，其中紫色表示新增的流量）
现在，$3\to T$ 这一条边满流了，于是这个图就有可行流了。我们得到的可行流的流量就是最大流上这一条边的流量加上原本的流量下界，也就是可行流长这样：
但是，这个可行流并不是最小流，因为还有很多的边还可以退回流量。于是，我们还需要使得流量最大或者最小化。
## 3. 可行流转最大流
在之前的可行流中，我们跑出来一些可行的流量，但是这并不意味着流量最大。有一些边还有一些剩余的流量，所以这并不是最大流。
怎么变成最大流呢？再跑一遍最大流。以实际的源点和汇点为源汇再跑一次最大流，注意不要让我们新增的源点和汇点影响最大流，所以我们要先把与新增的源点和汇点相连的所有边删了。然后，在**之前的残留网络**上再跑一次最大流，把可行流的流量加上最大流的流量即为答案。
比如之前的图，每一条边的剩余流量是这样的：
虽然这个图的最大流是 $0$，但是还会有一些其他图的最大流不是 $0$，所以再跑一遍是有必要的。
最后的最大流流量即为可行流流量加上最大流流量，比如这个图就是 $1+0=1$。
大家可以尝试去手摸一下其他样例。
还是比较好写的，因为不用写两套最大流，直接同一个最大流跑两遍就行了。注意：数组一定不要开小了。
::::success[code]
```cpp
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
const int M = 5e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m, s, t, u[M], v[M], l[M], r[M], bal[N], ss, tt, ef, idx, id[N], rf;
struct edge { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {
e[++ tot] = {v, w, head[u]};
head[u] = tot;
e[++ tot] = {u, 0, head[v]};
head[v] = tot;
}
int dis[N];
queue<int> q;
bool bfs(int s) {
memset(dis, 0, sizeof dis);
dis[s] = 1;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(e[i].w && !dis[v]) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t] != 0;
}
int cur[N];
int dfs(int u, int flow) {
if(u == t) return flow;
int delta = flow;
for(int i = cur[u]; i != -1; i = e[i].nex) {
cur[u] = i;
int v = e[i].to;
if(dis[v] == dis[u] + 1 && e[i].w) {
int f = dfs(v, min(delta, e[i].w));
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if(delta == 0) break;
}
}
return flow - delta;
}
int mf;
void dinic() {
mf = 0;
while(bfs(s)) {
memcpy(cur, head, sizeof cur);
mf += dfs(s, INF);
}
}
int main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m >> ss >> tt;
for(int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> l[i] >> r[i];
adde(u[i], v[i], r[i] - l[i]);//建第一次用来判可行的图
bal[v[i]] += l[i];
bal[u[i]] -= l[i];//更新节点流量差
}
s = n + 1;
t = n + 2;//建立新的超级源点和超级汇点
adde(tt, ss, INF);//无源汇转有源汇
idx = tot;//记录一下这一条边的id，之后要删掉
for(int i = 1; i <= n; i++) {
if(bal[i] > 0) {
adde(s, i, bal[i]);
ef += bal[i];//应该流的流量
}
if(bal[i] < 0) adde(i, t, -bal[i]);
}
dinic();
if(mf < ef) cout << "N\n";//没有满流，形不成可行流
else {
rf = e[idx].w;//记录之前可行流流量
e[idx].w = e[idx ^ 1].w = 0;//删掉之前的边
s = ss;
t = tt;//更新源点和汇点为题目要求的源汇
dinic();//再跑一遍最大流
cout << rf + mf << endl;//流量为两次流量之和
}
return 0;
}
```
::::
## 4. 可行流转最小流
在之前的可行流中，我们跑出来一些可行的流量，但是这并不意味着流量最小。有一些边还有一些多余的流量，所以这并不是最大流。
怎么变成最小流呢？我们想一想，要把尽可能多的流量退回去，那么我们就应该跑从汇点到源点的最大流，这个最大流就是能够从汇点向源点“退回去”的最大流量。再把之前的可行流减去这个流量，就是允许的最小流量。
比如之前的图，每一条边的剩余流量是这样的：
虽然这个图的最大流是 $0$，但是还会有一些其他图的最大流不是 $0$，所以再跑一遍是有必要的。
最后的最小流流量即为可行流流量减去最大流流量，比如这个图就是 $1-0=1$。
::::success[code]
```cpp
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
const int M = 5e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m, s, t, u[M], v[M], l[M], r[M], bal[N], ss, tt, ef, idx, id[N], rf;
struct edge { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {
e[++ tot] = {v, w, head[u]};
head[u] = tot;
e[++ tot] = {u, 0, head[v]};
head[v] = tot;
}
int dis[N];
queue<int> q;
bool bfs(int s) {
memset(dis, 0, sizeof dis);
dis[s] = 1;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(e[i].w && !dis[v]) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t] != 0;
}
int cur[N];
int dfs(int u, int flow) {
if(u == t) return flow;
int delta = flow;
for(int i = cur[u]; i != -1; i = e[i].nex) {
cur[u] = i;
int v = e[i].to;
if(dis[v] == dis[u] + 1 && e[i].w) {
int f = dfs(v, min(delta, e[i].w));
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if(delta == 0) break;
}
}
return flow - delta;
}
int mf;
void dinic() {
mf = 0;
while(bfs(s)) {
memcpy(cur, head, sizeof cur);
mf += dfs(s, INF);
}
}
int main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m >> ss >> tt;
for(int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> l[i] >> r[i];
adde(u[i], v[i], r[i] - l[i]);
bal[v[i]] += l[i];
bal[u[i]] -= l[i];
id[i] = tot;
}
s = n + 1;
t = n + 2;
adde(tt, ss, INF);
idx = tot;
for(int i = 1; i <= n; i++) {
if(bal[i] > 0) {
adde(s, i, bal[i]);
ef += bal[i];
}
if(bal[i] < 0) adde(i, t, -bal[i]);
}
dinic();
if(mf < ef) cout << "N\n";
else {
rf = e[idx].w;
e[idx].w = e[idx ^ 1].w = 0;
s = tt;
t = ss;
dinic();
cout << rf - mf << endl;
}
return 0;
}
```
::::
# 0x7 【模板】最小割树（Gomory-Hu Tree）
[link](https://www.luogu.com.cn/problem/P4897)。
最小割树用于求所有点对之间的最小割。根据最大流最小割定理，最大流等于最小割，所以在后面的分析里你们把最小割当最大流就行了。
最小割树的原理其实非常好理解，大致基于如下分析：
假如有一个大小为 $f$ 的割可以割开 $u$ 和 $v$，那么它也可以割开割集两边的任意点。因此，我们可以想到一种建树方法：
对于每一个计算出来的最小割，我们可以用树上的一条边来抽象这个割，这条边的两边分别为割集的两边所代表的节点，边权为这个割的大小，接着继续分治建树。需要注意的是，计算最小割需要在原图上跑。
可以画一些图来帮助理解（边默认为双向边）：
下面是初始状态：
假设第一次我们计算 $1\to 2$ 的割，容易得到最小割为 $6$，更新最小割树：
再次计算 $1\to 3$ 最小割可以得到 $7$ 的最小割值，更新最小割树如下：
最后再计算 $3\to 4$ 最小割，得到最终的最小割树：
容易发现现在每个点对之间的最小边权就是两两之间最小割。我们来分析一下复杂度：
由于每一次最大流会在这个树上建出一条边，树共有 $n-1$ 条边，可以知道会跑 $O(n)$ 次最大流，建树总复杂度 $O(n^3m)$。处理两两点对之间最小边权时间复杂度 $O(n^2)$，可以忽略。
主要就是代码巨难写。
::::success[code]
```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
using namespace std;
const int N = 500 + 10;
const int M = 1500 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
struct edge {
int to, w, nex;
void init(int _t, int _w, int _n) { to = _t; w = _w; nex = _n; }
} e[M * 2];
int tot, head[N];
struct e2 {
int u, v, w;
void init(int _u, int _v, int _w) { u = _u; v = _v; w = _w; }
} ebuf[M];
void rebuild() {//重建整张图
tot = -1;
memset(head, -1, sizeof head);
for(int i = 1; i <= m; i++) {
int u = ebuf[i].u, v = ebuf[i].v, w = ebuf[i].w;
e[++ tot].init(v, w, head[u]);
head[u] = tot;
e[++ tot].init(u, w, head[v]);
head[v] = tot;
}
}
int S, T, cur[N], dis[N];
queue<int> q;
bool bfs() {
memset(dis, 0, sizeof dis);
q.push(S);
dis[S] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(!dis[v] && e[i].w) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[T] != 0;
}
int dfs(int u, int flow) {
if(u == T) return flow;
int delta = flow;
for(int &i = cur[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(dis[v] == dis[u] + 1 && e[i].w) {
int f = dfs(v, min(delta, e[i].w));
delta -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if(delta == 0) break;
}
}
return flow - delta;
}
int dinic() {
int mflow = 0;
while(bfs()) {
memcpy(cur, head, sizeof cur);
mflow += dfs(S, INF);
}
return mflow;
}
vector<pair<int, int> > vt[N];
int v[N], lv[N], rv[N];
void build(int l, int r) {//建树
if(l >= r) return;
rebuild();//重新建出原图
S = v[l]; T = v[l + 1];
int mf = dinic();//最大流
vt[S].push_back(make_pair(T, mf));
vt[T].push_back(make_pair(S, mf));//加边，记得是双向边
int ltot = 0, rtot = 0;
for(int i = l; i <= r; i++) {
if(dis[v[i]]) lv[++ ltot] = v[i];//在割集左边的应该被放到左边继续分治
else rv[++ rtot] = v[i];//否则放到右边
}
for(int i = 1; i <= ltot; i++) v[l + i - 1] = lv[i];
for(int i = 1; i <= rtot; i++) v[l + ltot + i - 1] = rv[i];
build(l, l + ltot - 1);
build(l + ltot, r);//继续递归左边和右边
}
int cut[N][N];
bool vis[N];
void dfs2(int s, int u) {//树上 dfs 求点对间最小边权，相信大家都会
vis[u] = true;
if(u == s) cut[u][u] = INF;
for(int i = 0; i < vt[u].size(); i++) {
int v = vt[u][i].fi, w = vt[u][i].se;
if(!vis[v]) {
cut[s][v] = min(cut[s][u], w);
dfs2(s, v);
}
}
}
int main() {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
n ++;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
u ++; v ++;
ebuf[i].init(u, v, w);
}
for(int i = 1; i <= n; i++) v[i] = i;
build(1, n);
for(int i = 1; i <= n; i++) {
memset(vis, false, sizeof vis);
dfs2(i, i);
}
int Q;
cin >> Q;
while(Q--) {
int u, v;
cin >> u >> v;
u ++; v ++;
cout << cut[u][v] << endl;
}
return 0;
}
```
::::
# 0x8 【模板】有负圈的费用流
[link](https://www.luogu.com.cn/problem/P7173)。
最后一关！
对于有负权值的边，可以发现这一条边流量越大得到的答案就越优秀，所以我们考虑直接将这一条边满流。记得还是要建正向边和反向边，为了退流，只是流量反转而已。
现在我们发现了一件悲伤的事情：有一些点出入不平衡了。但是这个“出入不平衡”，不就正好是上下界网络流擅长处理的东西吗？于是思路如潮水般用来，这道题也就迎刃而解了。
我们建立超级源点和超级汇点，使用上下界网络流的思路建图，费用为 $0$，因为我们不希望这些多出来的边干扰我们的费用结果。然后，我们需要关心的就是上下界费用流该怎么求了。
其实很简单，就是把上下界最大流的最大流部分改成费用流，两次费用相互累加就行了。注意：我这里采用了上下界网络流的另一种写法：清零最大流之后不删边跑第二遍。这么做为什么是对的呢？由于影响到最大流的只有从汇点到源点的那一条边，而退流之后那一条边的反向边的边权正好是之前的流量，所以最大流求出来之后多的就正好是之前的流量！于是我们将流量清零之后再算一遍最大流跑出来之后是等价的。
代码就很好写啦~
::::success[code]
[评测记录](https://www.luogu.com.cn/record/266163165)
```cpp
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int M = 1e4 + 10;
const int N = 200 + 10;
const int INF = 0x3f3f3f3f;
struct edge { int to, nex, w, c; } e[M * 4];
int head[N], tot = -1, bal[N];
void adde(int u, int v, int w, int c) {
e[++ tot] = {v, head[u], w, c};
head[u] = tot;
}
int S, T, n, m, s, t, ans, sum, dis[N];
queue<int> q;
bool inq[N];
bool spfa(int s) {
for(int i = 1; i <= n + 2; i++) dis[i] = INF;
q.push(s);
inq[s] = true;
dis[s] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for(int i = head[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(dis[v] > dis[u] + e[i].c && e[i].w) {
dis[v] = dis[u] + e[i].c;
if(!inq[v]) {
q.push(v);
inq[v] = true;
}
}
}
}
return dis[T] != INF;
}
bool vis[N];
int cur[N];
int dfs(int u, int flow) {
if(u == T) return flow;
int delta = flow;
vis[u] = true;
for(int &i = cur[u]; i != -1; i = e[i].nex) {
int v = e[i].to;
if(e[i].w && !vis[v] && dis[v] == dis[u] + e[i].c) {
int f = dfs(v, min(delta, e[i].w));
e[i].w -= f;
e[i ^ 1].w += f;
delta -= f;
if(delta == 0) break;
}
}
vis[u] = false;
return flow - delta;
}
void dinic() {
while(spfa(S)) {
memcpy(cur, head, sizeof head);
int f = dfs(S, INF);
sum += f;
ans += dis[T] * f;
}
}
int main() {
memset(head, -1, sizeof head);
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++) {
int u, v, w, c;
cin >> u >> v >> w >> c;
if(c >= 0) {
adde(u, v, w, c);
adde(v, u, 0, -c);
} else {
adde(u, v, 0, c);
adde(v, u, w, -c);
bal[u] -= w;//在这里更新点的平衡，在c>=0分支不更新，是因为只有这里才会造成点出入不平衡，前面的分支其实是没有实际流量的
bal[v] += w;
ans += w * c;
}
}
S = n + 1, T = n + 2;
for(int i = 1; i <= n; i++) {
if(!bal[i]) continue;
if(bal[i] > 0) {//上下界网络流经典建图，费用为0
adde(S, i, bal[i], 0);
adde(i, S, 0, 0);
} else {
adde(i, T, -bal[i], 0);
adde(T, i, 0, 0);
}
}
dinic();
S = s, T = t, sum = 0;//清零最大流
dinic();
cout << sum << " " << ans << endl;
return 0;
}
```
::::