网络流

Alex_Wei · 2025-06-14 16:53:29 · 算法·理论

网络流的精髓在于建图。建图是人类智慧。

网络流本质上是贪心。网络流的建图刻画了问题本身的 可贪心 性质，从而简单地将问题的反悔操作统一为图上的网络流算法的反悔操作，使得我们不需要为每个问题都寻找对应的反悔策略。

1. 基本定义

一个网络流是一张 有向图 G = (V, E)。每条有向边 (x, y)\in E 有 容量 c(x, y) 和 流量 f(x, y)。特别地，若 (x, y)\notin E，则 c(x, y) = 0。f 称为网络流的 流函数。

注意

流函数对所有二元有序对均有定义，而不仅仅只是图上的边。

网络流的 可行流 分为有源汇和无源汇两种情况，常用 S 表示源点，T 表示汇点。一般认为源点没有入度，汇点没有出度。

可行流的流函数 f 满足以下性质：

• 容量限制：流量不超过容量。若 f(x, y) = c(x, y)，则称 x\to y 满流。
• 斜对称：f(x, y) = -f(y, x)。x\to y 有 1 的流量，也可以认为 y\to x 有 -1 的流量。
• 流量守恒：除源汇点以外（无源汇网络流不存在源汇点），从每个点流入和流出的流量相等。每个点不储存流量，流进多少就流出多少。

对于有源汇网络流，根据斜对称和容量守恒性质，从源点流出的总流量等于流入汇点的总流量。这个相等的值称为 f 的 流量。

将流的大小理解为单位时间可以流过多少体积的水（不可压缩液体）。对任何割，单位时间内从一侧流到另一侧的水的体积（流的流量）不超过割的容量。

结论

对于整数容量网络，存在一个流的流量等于一个割的容量。

证明

在有限次增广之后，在残量网络上，$S$ 和 $T$ 不连通，否则可以继续增广。设 $A$ 为残量网络上 $S$ 可达的所有点，$B$ 为剩下的所有点。 因为 $A$ 在残量网络上不可达 $B$，所以不可能有从 $B$ 到 $A$ 的边有流量（第一个等号），且 $A$ 到 $B$ 的所有割边满流（第二个等号）。因此，每单位流量恰好一次经过从 $A$ 到 $B$ 的割边， $$ |f| = \sum_{(x, y)\in (A, B)} f(x, y) = \sum_{(x, y)\in (A, B)} c(x, y) = c(A, B). $$ $\square

如果第一个集合的任意一个数不大于第二个集合的任意一个数，且存在第一个集合的一个数和第二个集合的一个数相等，那么第一个集合的最大值等于第二个集合的最小值。因此，最大流等于最小割。\square

最大流最小割定理告诉我们：如果在一个可行流的残量网络上 S 和 T 不连通，那么这个可行流是最大流。

最大流最小割定理也给出了整数容量网络的最大流算法：在残量网络上不断增广，直到残量网络不连通。但这个朴素的算法（Ford-Fulkerson，FF）的时间复杂度和流量有关，较劣。

2.3 Edmonds-Karp 算法

算法介绍

任意选择增广路不优秀，那就选择具有一定性质的增广路。

Edmonds-Karp 算法的核心是使用 BFS 寻找 长度最短 的增广路。为此，对当前增广路上的每个点，我们记录流向这个点的边的编号（方便修改容量），然后从汇点 T 不断回推到源点 S。时间复杂度 \mathcal{O}(n m ^ 2)。

模板题 代码如下。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200 + 5, M = 5e3 + 5;
struct flow {
  ll fl[N], limit[M << 1];
  int cnt = 1, hd[N], nxt[M << 1], to[M << 1], fr[N];
  void add(int u, int v, int w) {
    nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v, limit[cnt] = w;
    nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u, limit[cnt] = 0;
  }
  ll maxflow(int s, int t) {
    ll flow = 0;
    while(1) {
      queue<int> q;
      memset(fl, -1, sizeof(fl));
      fl[s] = 1e18, q.push(s);
      while(!q.empty()) {
        int t = q.front();
        q.pop();
        for(int i = hd[t]; i; i = nxt[i]) {
          int it = to[i];
          if(limit[i] && fl[it] == -1) { // 若剩余流量为 0, 那么在残量网络上不存在, 不能走
            fl[it] = min(limit[i], fl[t]); // 记录流量
            fr[it] = i, q.push(it); // 记录流向每个点的边的编号
          }
        }
      }
      if(fl[t] == -1) return flow;
      flow += fl[t];
      for(int u = t; u != s; u = to[fr[u] ^ 1]) {
        limit[fr[u]] -= fl[t];
        limit[fr[u] ^ 1] += fl[t]; // 从 T 一路反推到 S，并更新每条边的剩余流量
      }
    }
  }
} g;
int n, m, s, t;
int main() {
  cin >> n >> m >> s >> t;
  for(int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w, g.add(u, v, w);
  }
  cout << g.maxflow(s, t) << endl;
  return 0;
}

复杂度证明

为证明 EK 算法的时间复杂度，我们需要这样一条引理：

引理

每次增广后残量网络上 S 到每个点的最短路长度 不减。

证明

考虑从 S 出发的最短路 DAG 的分层图。新加入的边一定是从 dis 较大的点指向 dis 较小的点。\square

设原残量网络的最短路长度为 dis。

如果最短路长度减小了，那么在新的最短路上，总存在一条边 x\to y 使得 dis_x + 1 < dis_y。这条边不可能是原残量网络的边，否则就不满足三角形不等式了。所以 x\to y 一定是新加入的边，即 y\to x 被增广。一条边被增广需要它在最短路上，所以

dis_y + 1 = dis_x < dis_x + 1 < dis_y.

矛盾。

设增广路为 P。根据能流满就流满的原则，存在 x\to y 使得其剩余流量 c_f(x, y) 等于本次增广流量 c_f(P)。于是，x\to y 属于原来的残量网络，但不在增广后的残量网络上。称这种边为 关键边。

因为增广路是最短路，dis_x + 1 = dis_y。在使得 x\to y 再次出现在残量网络上的增广之前，dis'_y + 1 = dis'_x。所以

因此 x\to y 每次在残量网络上消失又出现的过程必然使得 dis_x 至少增加 2。

综上，每条边作为关键边的次数不超过 \mathcal{O}(n)。因为一次增广必然存在关键边，所以增广次数不超过 \mathcal{O}(nm)，时间复杂度 \mathcal{O}(nm ^ 2)。

注

从复杂度分析的过程来看，这个上界是很宽松的。虽然总能构造特殊图卡满上界（同阶），但常数非常小。

2.4 Dinic 算法

算法介绍

Dinic 算法的核心思想是 分层图 和 相邻层之间增广。首先 BFS 得到分层图，然后从 S 出发进行 DFS 多路增广。维护当前点的剩余流量，向下一层的点继续流。

给图分层，将本次增广限制在 DAG 上的目的是规范增广路的形态，防止增广路成环。

当前弧优化 保证了 Dinic 算法的时间复杂度。增广时，已经流满的边没有用，可以直接跳过，不需要每次都从邻接表头开始遍历。为此，记录从每个点出发的第一条没有流满的边，称为 当前弧。搜索到一个点时，从其当前弧开始增广。

注意

每次多路增广前每个点的当前弧应初始化为邻接表头。一条边并非一旦流满就无用。反向边流量的增加会让它重新出现在残量网络中。

当前弧优化后的 Dinic 算法的时间复杂度 \mathcal{O}(n ^ 2m)。若不加当前弧优化，时间复杂度会退化成和 EK 一样的 \mathcal{O}(nm ^ 2)。此时由于 DFS 常数过大，实际表现并没有 EK 优秀。

注

Dinic 实际上蕴含了 EK，因为 Dinic 本质也是找最短路增广。相较于 EK，Dinic 加入了多路增广和当前弧优化。

当前弧优化的注意点

for(int i = cur[u]; res && i; i = nxt[i]) {
  cur[u] = i;
  // do something
}

上述代码不可以写成

for(int &i = cur[u]; res && i; i = nxt[i]) {
  // do something
}

若 u\to v 这条边让剩余流量 res 变成 0，第二种写法会使 u 的当前弧直接跳过 u\to v。但 u\to v 不一定流满，所以不应跳过。这会导致当前弧跳过很多未流满的边，使增广效率降低，从而大幅降低程序运行效率。实际表现比 E-K 还要差。

另一种解决方法是在循环末尾判断 if(!res) return flow;。总之，在写当前弧优化时注意不能跳过没有流满的边。

模板题 代码如下。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200 + 5, M = 5e3 + 5;
struct flow {
  int cnt = 1, hd[N], nxt[M << 1], to[M << 1], limit[M << 1];
  void add(int u, int v, int w) {
    nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v, limit[cnt] = w;
    nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u, limit[cnt] = 0;
  }
  int T, dis[N], cur[N];
  ll dfs(int id, ll res) {
    if(id == T) return res;
    ll flow = 0;
    for(int i = cur[id]; i && res; i = nxt[i]) {
      cur[id] = i;
      int c = min(res, ll(limit[i])), it = to[i];
      if(dis[id] + 1 == dis[it] && c) {
        int k = dfs(it, c);
        flow += k, res -= k;
        limit[i] -= k, limit[i ^ 1] += k;
      }
    }
    if(!flow) dis[id] = -1;
    return flow;
  }
  ll maxflow(int s, int t) {
    T = t;
    ll flow = 0;
    while(1) {
      queue<int> q;
      memcpy(cur, hd, sizeof(hd));
      memset(dis, -1, sizeof(dis));
      q.push(s), dis[s] = 0;
      while(!q.empty()) {
        int t = q.front();
        q.pop();
        for(int i = hd[t]; i; i = nxt[i]) {
          if(dis[to[i]] == -1 && limit[i]) {
            dis[to[i]] = dis[t] + 1, q.push(to[i]);
          }
        }
      }
      if(dis[t] == -1) return flow;
      flow += dfs(s, 1e18);
    }
  }
} g;
int n, m, s, t;
int main() {
  cin >> n >> m >> s >> t;
  for(int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w, g.add(u, v, w);
  }
  cout << g.maxflow(s, t) << endl;
  return 0;
}

复杂度证明

在证明 EK 的时间复杂度时，我们用到了结论：S 到每个点的最短路单调不减。因为 Dinic 蕴含 EK，所以该引理仍然成立。

考虑增广轮数和一轮增广的复杂度。

结论

Dinic 的每次增广都会使得 S 到 T 的最短路长度增加。

证明

反证法。假设存在一次增广使得 S 到 T 的最短路长度没有增加。由引理，S 到 T 的最短路不变。

由一轮增广的过程，S 到 T 的最短路 P 不可能是原残量网络上的最短路（否则会被增广掉）。于是存在 (x, y)\in P 使得 dis_x + 1 < dis_y。类似引理的证明可以导出矛盾。\square

于是增广轮数为 \mathcal{O}(n) 级别。

DFS 时，每次到达 T 都代表找到一条增广路。我们将寻找这条增广路的代价放大至增广路的长度，即 \mathcal{O}(n)。实际远达不到这一上界（但仍然是 \mathcal{O}(n)，达不到上界指常数非常小）。

找到增广路后，我们将不断回溯，直到当前点还有多余的流量。那么增广路上从这个点出发的那条边（也就是关键边）将满流。因此增广路的数量不超过 \mathcal{O}(m)。

综上，一次增广的复杂度为 \mathcal{O}(nm)。可以看出这个上界非常松，这也是为什么 Dinic 算法在求网络最大流时表现良好。

3. 无负环的费用流

费用流一般指 最小费用最大流 minimum cost maximum flow, MCMF。

在原网络 G 的基础上，每条边有 权值 w(x,y)。最小费用最大流要求保证最大流时 \sum_{(x,y)\in E} f(x, y)\times w(x, y) 的最小值。w 即每条边流单位流量的费用，我们需要在最大流的前提下最小化费用，因此该问题称为费用流。

本章讨论 初始残量网络无负环 的费用流。关于有负环的费用流，见 6.2 小节。

3.1 SSP 算法

算法介绍

连续最短路 successive shortest path，简称 SSP。该算法的核心思想是每次找到 长度最短的增广路 进行增广。仅在网络 初始无负环 时能得到正确答案。

SSP 算法有两种实现方法，一种基于 EK，另一种基于 Dinic。这两种方法均需要将 BFS 换成 SPFA（每条边的长度为 w）求最短路，且 Dinic 的 DFS 多路增广仅在满足 dis_x + w(x, y) = dis_y 的边上进行。

注意

在使用 SPFA 求 S 到 T 的最短路时，不能在队头为 T 时就退出算法，因为此时 dis[T] 不一定取到最短路。

退流 x\to y 时，其费用也要退掉。因此，对原图的每条边 x\to y，其在残量网络上的反边的权值 w(y, x) 为 -w(x, y)。

注意

原图上的一条边和它的反边是独立的，它们在残量网络上有各自独立的反边（见基本定义最后一段），所以权值不冲突。

SSP 算法的时间复杂度为 \mathcal{O}(nmf)，其中 f 是最大流流量，这说明 SSP 算法是伪多项式时间的。在实际应用中，该上界非常宽松。不仅增广次数远远达不到 f，同时 SPFA 的时间也远远达不到 \mathcal{O}(nm)，可以放心使用。

注

一般以 Dinic 作为网络最大流的标准算法，以基于 EK 的 SSP 作为费用流的标准算法。

「最大流不卡 Dinic，费用流不卡 EK」是业界公约。

模板题 代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5, M = 5e4 + 5;
struct flow {
  int cnt = 1, hd[N], nxt[M << 1], to[M << 1], limit[M << 1], cst[M << 1];
  void add(int u, int v, int w, int c) {
    nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v, limit[cnt] = w, cst[cnt] = c;
    nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u, limit[cnt] = 0, cst[cnt] = -c;
  }
  int fr[N], fl[N], in[N], dis[N];
  pair<int, int> mincost(int s, int t) {
    int flow = 0, cost = 0;
    while(1) { // SPFA
      queue<int> q;
      memset(dis, 0x3f, sizeof(dis));
      memset(in, 0, sizeof(in));
      fl[s] = 1e9, dis[s] = 0, q.push(s);
      while(!q.empty()) {
        int t = q.front();
        q.pop(), in[t] = 0;
        for(int i = hd[t]; i; i = nxt[i]) {
          int it = to[i], d = dis[t] + cst[i];
          if(limit[i] && d < dis[it]) {
            fl[it] = min(limit[i], fl[t]), fr[it] = i, dis[it] = d;
            if(!in[it]) in[it] = 1, q.push(it);
          }
        }
      }
      if(dis[t] > 1e9) return make_pair(flow, cost);
      flow += fl[t], cost += dis[t] * fl[t];
      for(int u = t; u != s; u = to[fr[u] ^ 1]) {
        limit[fr[u]] -= fl[t], limit[fr[u] ^ 1] += fl[t];
      }
    }
  }
} g;
int n, m, s, t;
int main() {
  cin >> n >> m >> s >> t;
  for(int i = 1; i <= m; i++) {
    int u, v, w, c;
    cin >> u >> v >> w >> c, g.add(u, v, w, c);
  }
  pair<int, int> ans = g.mincost(s, t);
  cout << ans.first << " " << ans.second << endl;
  return 0;
}

SSP 算法的时间复杂度是显然的：一次 SPFA 是 \mathcal{O}(nm)，最多增广 f 次。

正确性证明

我们证明每次增广最短路一定能求出最小费用最大流。根据最大流最小割定理可证流的最大性，因此只需证明费用最小性。

考虑两个流量相等的可行流 f_1, f_2，令 \Delta f = f_2 - f_1，则 \Delta f 流量为零，所以 \Delta f 由若干个正流量的环组成。若 f_2 的费用小于 f_1，则 \Delta f 包含至少一个正流量的负环。

消圈定理

**证明** 若 $f$ 的残量网络含负环，在负环上推流可以得到流量相等但费用更小的流。 若 $f$ 不是费用最小的流，则存在流 $f'$ 使得 $\Delta f = f' - f$ 包含正流负环，于是 $f$ 的残量网络有负环。$\square

归纳假设增广前 f 的残量网络无负环。设增广后的流为 f'。不妨设流量的增量为 1，则费用的增量为最短路的长度。

假设存在流 f'' 的流量与 f' 相等但费用更小。因为流量增量为 1，所以 f'' - f 由 S 到 T 的流量为 1 的路径 P' 和一些正流量的环 C_1, \cdots, C_k 组成。因为 f' - f 是最短路，所以 P' 的费用不小于 f\to f' 的费用。但 f\to f'' 的费用小于 f \to f' 的费用，所以存在负环 C_i，矛盾。

因此，不存在流量与 f' 相等但费用更小的流。由消圈定理，f' 的残量网络上无负环。因为初始网络无负环，所以归纳法成立。\square

3.2 Primal-Dual 算法

建议先学习 Johnson 全源最短路算法，详见 图论 I。

注

Primal-Dual 原始对偶实际上是一个重要的组合优化技术。但是笔者并没有看出以下算法和它的关联。

和 SSP 一样，Primal-Dual 仅适用于无负环的网络。

算法尝试为每个点赋势能 h_i，保持原图最短路不变的同时让边权非负。这个目标和 Johnson 全源最短路的第一步如出一辙。

首先使用 SPFA 求出源点到每个点的最短路 h_i，则 i\to j 的新边权为 w'_{i, j} = w_{i, j} + h_i - h_j。根据三角形不等式，w'_{i, j} \geq 0。因此，经过转化，我们可以使用更稳定的 Dijkstra 求增广路。

每次增广都会改变残量网络的形态。为此，用每次增广时跑出来的最短路加在 h 上，即 h'_i\gets h_i+dis_i。

正确性证明

如果 i\to j 在增广路上，有 dis_i + w_{i, j} + (h_i - h_j) = dis_j。因为 w_{i, j} = -w_{j, i}，所以 w_{j, i} + (dis_j + h_j) - (dis_i + h_i) = 0，即新增的反边边权为 0。

对于原有的边，dis_i + w_{i, j} + (h_i - h_j) \geq dis_j，即 w_{i, j} + (dis_i + h_i) - (dis_j + h_j)\geq 0，原边权仍然非负。

\square

实际表现方面，Primal-Dual 相较于 SSP 并没有很大的优势，可能是因为 SPFA 本身已经够快了。而且 Primal-Dual 写起来没有 SSP 方便。

代码。

4. 上下界网络流

在原网络 G 的基础上，每条边有 流量下界 b(u, v)。这使得可行的流函数应满足的流量限制更加严格：b(u, v)\leq f(u, v)\leq c(u, v)。

4.1 无源汇可行流

无源汇上下界可行流是上下界网络流的基础。我们需要为一张无源汇的网络寻找一个流函数 f，使其满足流量限制，斜对称以及流量守恒。解决这个问题的核心思想，是 先满足流量下界的限制，再尝试调整。

具体地，我们首先让每条边 (u, v) 都 流满下界 b(u, v)，并算出每个点的 净流量 w_i，即流入 i 的总流量减去从 i 流出的总流量。

当 w_i > 0 时，说明当前流到 i 的流量太多了，还要再流出去 w_i 才能守恒。相反，若 w_i < 0，说明 i 还要流进 -w_i 单位流量。根据斜对称性，有 \sum w_i = 0。由此可设 \Delta = \sum_{w_i > 0} w_i = \sum_{w_i < 0} -w_i。

这启发我们新建无容量下界的网络 G' \approx G，每条边的流量限制 c' = c - b，并认为最终的可行流 f 为 b 加上 G' 上的可行流 f'。

新建独立于原有点集的超级源点 SS 和 超级汇点 TT（虽然 G 无源无汇，但这是为了区分有源汇时不同最大流过程的源点和汇点）。若 w_i > 0，则连边 SS\to i 容量为 w_i，否则连边 i\to TT 容量为 -w_i。不难发现，从 SS 连出了总容量为 \Delta 的边，且总容量为 \Delta 的边连向了 TT。

注意

初学者容易搞反连边的方式。我们可能会认为，如果 w_i > 0，即流到 i 的流量太多了，那应该连边 i\to TT 容量为 w_i，把这些流量流走才对。原因是最终可行流的定义 f = b + f'。在 b 中 i 的净流量为 w_i，所以 f' 在原图上的那部分（即去掉 i 和超源或超汇的连边）的净流量应当为 -w_i。为了让 f' 本身是流量守恒的，需连边 SS\to i 补充 w_i 流量。

换言之，SS 和 TT 的连边起到了 模拟 每个点的净流量的作用，而非补充或消耗。

为了让每个点的净流量变为 0，所有超源和超汇相关的连边必须流满。于是，若 SS 到 TT 的最大流 f' 的流量不等于 \Delta，说明找不到一种合法方案使得同时满足流量限制和流量守恒，问题无解。相反，若最大流等于 \Delta，则将 f' 的流量加在 b 上，得到可行流 f = b + f'。

• 因为 SS 到 TT 满流，所以 f 的每个点的净流量均为 0。
• 因为 G' 上的流量限制是在每条边在 b 的基础上还能流多少，所以 f 满足流量限制，即 f = f' + b\leq c' + b = c。

代码。

4.2 有源汇可行流

连边 T\to S 容量为 +\infty，转化为无源汇上下界可行流。

4.3 有源汇最大流

有源汇上下界最大流基于一个非常关键的结论：给定任意一组 可行流，对其运行 EK 或 Dinic 等基于增广操作的最大流算法，我们总能得到正确的最大流。因为增广本身支持退流，所以无论初始的流函数 f 如何，只要 f 合法，就一定能求出最大流。

因此，我们考虑先求出任意一组可行流，再进行调整：首先对 G 求有源汇 可行流，过程中我们会新建网络 G'。撤去 SS, TT 以及 T\to S 的容量为 +\infty 的边。SS, TT 的意义是求无源汇可行流，T\to S 的意义是将有源汇可行流转化为无源汇可行流，而我们已经得到了一组有源汇可行流，除非转化的无源汇可行流问题无解。当前可行流流量即 T\to S 的流量，即残量网络上的反边的容量。

注意

可行流流量是 T\to S 的反边流量，而不是 SS 到 TT 的流量。

根据开头给出的结论，我们只需要以 S 为源，T 为汇在 \color{red} G' 上跑最大流，并将可行流流量与最大流流量（新增流量）相加即为有源汇最大流。注意与 SS, TT 作区分。

注意

二次调整在 G' 上进行，不能在 G 上面跑最大流，因为 G 的退流操作会使得 f 不符合容量限制，但 G' 的退流操作不会。

因为 G 的实际流量 f 等于 b + f'，所以只要 f' 符合容量限制，那么 f 也一定符合。

代码。

4.4 有源汇最小流

根据 S 到 T 的最小流等于 T\to S 的最大流的相反数这一结论，用可行流减掉 G' 上 T\to S 的最大流。

代码。

4.5 无源汇费用流

将最大流算法换成费用流，所有和 SS, TT 相关的连边代价均为 0。因为 G' 相较 G 只增加了 SS 和 TT 的边，所以 G' 无负环当且仅当 G 无负环。

初始费用为 \sum b(x, y)w(x, y)。需加上调整净流量所产生的费用，即 SS 到 TT 的最小费用最大流的费用。

4.6 有源汇费用流

注意连边 T\to S 可能导致网络出现负环，所以通常使用下一小节的技巧消去图上的负权边。

对于有源汇最小费用最大流，在有源汇最小费用可行流的基础上，进行二次调整时也要加上产生的费用。特别地，二次调整前删去 SS, TT 和 T\to S 不会让残量网络出现负环。

4.7 有负环的费用流

有负环不影响最小费用存在，因为有流量限制。

注

对于有源汇的情况，允许成环的流量不经过 S 和 T，否则可以 “挑战哈密顿”：所有边的费用为 -1。建超源 SS 连边 SS\to S 容量为 1 且费用为 0 以限制流量为 1，则 S 到 T 存在哈密顿路径当且仅当最小费用最大流的费用为 1 - n。

考虑上下界网络流，强制令负权边满流，加入反边 b(y, x) = 0，c(y, x) = c(u, v) 表示退流。此时，负权边的流量等于容量，所以不会出现在 G' 中，初始残量网络无负环。使用上一小节的上下界费用流算法即可。

称为 消圈算法。

最大费用最大流：将边权取反，求可能有负环的费用流。

模板题 代码如下。

#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 5, M = 2e4 + N;
struct flow {
  int cnt = 1, hd[N], nxt[M << 1], to[M << 1], limit[M << 1], cst[M << 1];
  void add(int u, int v, int w, int c) {
    nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v, limit[cnt] = w, cst[cnt] = c;
    nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u, limit[cnt] = 0, cst[cnt] = -c;
  }
  int fl[N], fr[N], dis[N], in[N];
  pair<int, int> mincost(int s, int t) {
    int flow = 0, cost = 0;
    while(1) {
      queue<int> q;
      memset(dis, 0x3f, sizeof(dis));
      q.push(s), fl[s] = 1e9, dis[s] = 0;
      while(!q.empty()) {
        int t = q.front();
        q.pop(), in[t] = 0;
        for(int i = hd[t]; i; i = nxt[i]) {
          int it = to[i], d = dis[t] + cst[i];
          if(limit[i] && d < dis[it]) {
            dis[it] = d, fl[it] = min(fl[t], limit[i]), fr[it] = i;
            if(!in[it]) in[it] = 1, q.push(it);
          }
        }
      }
      if(dis[t] > 1e9) return make_pair(flow, cost);
      flow += fl[t], cost += dis[t] * fl[t];
      for(int u = t; u != s; u = to[fr[u] ^ 1]) {
        limit[fr[u]] -= fl[t], limit[fr[u] ^ 1] += fl[t];
      }
    }
  }
};
struct bounded_flow {
  int e, u[M], v[M], lo[M], hi[M], cst[M];
  void add(int _u, int _v, int w, int c) {
    if(c < 0) {
      u[++e] = _u, v[e] = _v, lo[e] = w, hi[e] = w, cst[e] = c;
      u[++e] = _v, v[e] = _u, lo[e] = 0, hi[e] = w, cst[e] = -c;
    }
    else u[++e] = _u, v[e] = _v, lo[e] = 0, hi[e] = w, cst[e] = c;
  }
  flow g;
  pair<int, int> mincost(int n, int s, int t, int ss, int tt) {
    static int w[N];
    memset(w, 0, sizeof(w));
    int flow = 0, cost = 0, tot = 0;
    for(int i = 1; i <= e; i++) {
      w[u[i]] -= lo[i], w[v[i]] += lo[i];
      cost += lo[i] * cst[i];
      g.add(u[i], v[i], hi[i] - lo[i], cst[i]);
    }
    for(int i = 1; i <= n; i++) {
      if(w[i] > 0) g.add(ss, i, w[i], 0), tot += w[i];
      else if(w[i] < 0) g.add(i, tt, -w[i], 0);
    }
    g.add(t, s, 1e9, 0);
    pair<int, int> res = g.mincost(ss, tt);
    cost += res.second;
    flow += g.limit[g.hd[s]];
    g.hd[s] = g.nxt[g.hd[s]], g.hd[t] = g.nxt[g.hd[t]];
    res = g.mincost(s, t);
    return make_pair(flow + res.first, cost + res.second);
  }
} f;
int n, m, s, t;
int main() {
  cin >> n >> m >> s >> t;
  for(int i = 1; i <= m; i++) {
    int u, v, w, c;
    cin >> u >> v >> w >> c, f.add(u, v, w, c);
  }
  pair<int, int> res = f.mincost(n, s, t, 0, n + 1);
  cout << res.first << " " << res.second << endl;
  return 0;
}

4.8 总结

先满足流量下界的限制，转化成无下界限制的情形，再调整。

无源汇可行流：最基本的情况，算出每个点的净流量后最大流调整。

有源汇可行流：加入 T\to S 转化为无源汇可行流。

有源汇最大流：先求可行流，在删去 SS, TT 和 T\to S 的 G' 上跑 S 到 T 的最大流。

有源汇最小流：先求可行流，在删去 SS, TT 和 T\to S 的 G' 上跑 T 到 S 的最大流。

若带有费用，则将最大流换成最小费用最大流。通过取反将最大费用转化为最小费用。需要保证运行费用流算法的网络（G'）无负环，可以用消圈算法除去所有负权边。

5. 对网络流的理解

网络流的本质是反悔贪心。解决网络流问题分成两步：相信问题可以用网络流算法解决，建图。

5.1 网络流与贪心

在网络流算法中，我们的策略是贪心地找到最短路进行增广。但这样的决策不一定最优，需要为反边添加容量。流过反边即退掉流量，对应原问题的 反悔 操作。因此，网络流本质上是 可反悔贪心。运用上下界网络流等技巧可以方便地处理问题的限制。

更一般地，网络流也是一种特殊的贪心，它们之间可以相互转化。对于具有特定增广模式（网络具有某种性质）的网络流，可以从贪心的角度考虑，从而使用数据结构维护，称为 模拟费用流。很多贪心问题也可以通过网络流解释。

换言之，网络流 将贪心以图的形式刻画。解决网络流问题的算法与某个支持反悔的贪心策略相对应，使得我们不需要为每个贪心问题都寻找反悔策略。相反，建出图后就是一遍最大流或费用流的事了。

注意

因为网络流算法本身自带反悔操作，所以在解决动态加边的 最大流 问题时，我们不需要担心原来的流方案会影响到算法求解新图最大流时的正确性。

但对于费用流，因为其正确性依赖于每一步增广路均为最短路，所以一旦给网络加入新边，就必须重新跑费用流才能得到正确费用（或者根据消圈定理，要求加边后残量网络无负环）。

5.2 网络流的技巧

解决可以转化为网络流的最优化问题，关键在于如何建图，将问题的限制转化为图上的边，使得 问题的每种方案都与一种流或割对应。最大化问题考虑最大流或转化为最小割，最小化问题考虑最小割。

例如，在 P2057 一题中，直接对每个小朋友拆点并不可行，因为无法考虑到他与他的朋友意见不一致时的代价。题目要求最小化代价，所以考虑用一组割表示一种意见方案。一个点在割中要么属于 A，要么属于 B，正好刻画了一个小朋友要么支持，要么反对。不妨认为属于 A 表示支持，属于 B 表示反对。

• 如果 i 原本支持但 i\in B，则有 1 的代价。如何让 i\in B 有 1 的代价？连边 S\to i 容量为 1。i\in B 说明 S\to i 被割掉，产生 1 的代价。
• 类似地，如果 i 原本反对，则连边 i\to T 容量为 1，i\in A 说明 i\to T 被割掉，产生 1 的代价。对应 i 原本反对但 i\in A，意愿不同，有 1 的代价。
• 如何刻画投票不同的好朋友的代价？若 i\in A，j\in B 且 i, j 互为好朋友，则有 1 的代价。因为 i\in A，j\in B，所以 i\to j 若存在则一定是割边。连边 i\to j 容量为 1 即可。

对于一组割，其唯一对应了一个投票方案。残量网络上属于 A 的人支持，属于 B 的人反对。这是经典的 集合划分模型。

5.3 求方案时的注意点

在尝试根据最大流求最小割时，初学者可能会陷入一个误区，认为满流的边即割边。这显然是错误的，反例如 c(S, 1) = c(1, T) = 1。

回忆割的定义：将 V 分成两个互不相交的点集 A, B 满足 S\in A 且 T\in B，则所有 A\to B 的边才是割边。最大流最小割的证明自然地给出了一组割：若 S 可达 u，则 u\in A，否则 u\in B。

因此，若一组割对应了题目的一种方案，在求出最大流之后，不能将流满的边视作割边，而是将两端所在集合不同的边视作割边。在使用集合划分模型求方案时需格外注意。

6. 常见模型和问题

其实是常见建图套路。

6.1 最小割点

题目描述

给定删去每个点的代价 w_i，求使得 S, T 不连通的最小代价。

之前的最小割都是割边。

点边转化 是网络流的常用技巧。将每个点拆成入点 i_{in} 和出点 i_{out}，连边 i_{in}\to i_{out} 容量为 w_i，表示删去这个点使得 i_{in} 与 i_{out} 不连通需要 w_i 的代价。对原图的每一条边 (u, v)，连边 u_{out}\to v_{in} 容量为 +\infty，表示只能删点，不能删边。

不难发现 S_{out} 到 T_{in} 的最小割即为所求。

例题：P1345，P3356，P2045，P2153。

*6.2 集合划分模型

集合划分模型是网络流常见模型。这个模型应用广泛，可以加深对最小割问题的理解，读者应充分掌握。

问题描述

有 n 个物品，A, B 两个集合。物品 i 分到集合 A 有代价 a_i，分到集合 B 有代价 b_i。给定 m 条限制 (u_j, v_j, c_j)，表示若 u_j\in A 且 v_j\in B，则有代价 c_j。求最小代价。

复杂度只能和 n, m 有关。

注

一种等价形式为

\min_{x_{1\sim n}} \left(\left(\sum_{u = 1} ^ n a_u x_u\right) + \left(\sum_{u = 1} ^ n b_u \overline{x_u}\right) + \left(\sum_{(u, v)\in E} c_{u, v} x_u \overline{x_v}\right)\right),

其中 x_i 等于 0 或 1，\overline{x_i} 表示 x_i 取反。x_i = 1 表示分到 A，x_i = 0 表示分到集合 B。

给定 a, b, c, E，为 x_i 选择合适的值最小化整个和式。

建出网络：

• 连边 S\to i 容量为 b_i，表示若 i\in B 则 S\to i 被割掉，代价为 b_i。
• 连边 i\to T 容量为 a_i，表示若 i\in A 则 i\to T 被割掉，代价为 a_i。
• 连边 u_j\to v_j 容量为 c_j，表示若 u_j\in A 且 v_j\in B 则 u_j\to v_j 被割掉，代价为 c_j。