网络流最小割：从“切断补给线”到“追查坏牛奶”

如果说最大流是“如何用最快的速度把水从A送到B”，那么最小割就是“如何用最少的代价切断A到B的所有通路”——它用一张网络和一把“剪刀”，回答了所有阻断问题的最优解。

引言

假设你是一名指挥官，敌军有一条从后方基地到前线的补给线网络——多条道路交织，四通八达。你的任务是：炸掉最少的道路（或者说花费最小的代价），让补给彻底无法送达前线。每条道路的炸毁成本不同，你该怎么选？

这个问题在算法竞赛中有一个标准的数学模型——最小割（Minimum Cut） 。而“最大流等于最小割”这条定理，则是解决这类问题的核心武器。

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。送货网很大，关系复杂，坏牛奶已经进入了这个网络。你的任务是，在保证坏牛奶不送到零售商（节点N）的前提下，停止某些运输卡车，使损失最小——同时，在损失最小的前提下，还要让停止的卡车数量最少。

这就是洛谷 P1344 [USACO4.4] 追查坏牛奶 Pollutant Control 要解决的问题。

“如果说网络流是图论中的‘水利工程’，那么最小割就是它的‘定向爆破’——你不需要关心水怎么流，只需要知道在哪里切断最划算。”

前置知识

在阅读本文之前，建议你熟悉以下概念：

第一章：从“割”说起——最小割是什么

1.1 割的定义：把图一分为二

在一个流网络中，一个 割（Cut） 就是把所有节点分成两个集合——SS和TT，满足源点s∈S，汇点t∈T。

割的 容量（Capacity） 定义为：所有从S指向T的边的容量之和。

换句话说，割的容量就是你为了切断s到t的所有通路，需要“剪掉”的那些边的总容量。

1.2 最小割：最便宜的“断交”方案

最小割（Minimum Cut） ，就是在所有可能的割中，容量最小的那个割。

为什么最小割重要？因为它回答了一个核心问题：切断源点到汇点的所有路径，最少需要付出多少代价？

这正好对应了P1344的第一问——“使坏牛奶无法送达零售商的最小经济损失”。

1.3 一个生活中的类比

想象一个供水网络：自来水厂（源点）向你家（汇点）供水，中间经过无数管道和水闸。现在政府要检修管道，需要关闭一些水闸让你家暂时停水。每个水闸的关闭成本不同——有的闸门锈了很难关（成本高），有的很好关（成本低）。最小割就是告诉你：关哪些水闸，既能让水完全停掉，又花最少的钱。

这就是最小割的直觉——花最少的代价，彻底阻断。

第二章：最大流最小割定理——解决问题的“核武器”

2.1 定理的直观理解

最大流最小割定理（Max-Flow Min-Cut Theorem） 是网络流理论中最核心的定理之一：

在一个流网络中，从源点到汇点的最大流量，等于最小割的容量。

这个定理为什么成立？直观上可以这样理解：

• 最大流不可能大于最小割：因为所有从s到t的流量都必须经过任意一个割，而割的容量限制了能通过的总流量。

• 最大流不可能小于最小割：如果最大流小于某个割的容量，说明网络还没有被充分利用，可以继续增广。

所以两者必然相等。

2.2 定理的证明思路（简要）

严格的证明通常分两步：

因此，最大流 = 最小割。

2.3 这个定理给我们的“便利”

这个定理最大的实用价值在于：求最小割，等价于求最大流。

也就是说，我们不需要单独设计一个“求最小割”的算法——只需要跑一遍最大流（比如Dinic算法），得到的最大流数值就是最小割的容量。

在P1344中，第一问“最小的经济损失”，就是直接跑最大流的结果。

第三章：P1344的挑战——不仅要最小，还要最少

3.1 题目的两个要求

P1344要求输出两个整数：

第一问很简单——直接建图跑最大流。

难点在第二问：最小割可能有多种方案，我们要从中选出边数最少的那一个。也就是说，在“最小损失”和“最少停运卡车数”之间，前者优先级更高。

3.2 朴素思路的问题

一个直观的想法是：先跑一遍最大流求出最小割的容量，然后把所有边的容量改成1，再跑一遍最大流，得到最少边数。

这样做确实可行，但要跑两遍网络流，代码量大、常数也大。在算法竞赛中，我们追求更优雅的一次建图、一次跑流的解法。

3.3 核心技巧：边权编码

既然要同时优化两个目标——主目标（损失最小）优先级高于辅目标（边数最少）——我们可以把两个目标“编码”到同一条边的容量中。

具体做法是：将每条边的容量从 w 改为 w×K+1，其中 KK 是一个大于总边数 MM 的数。

为什么这样做？设一个割包含 kk 条边，其容量为：

∑(wi×K+1)=K×∑wi+k

• 第一部分 K×∑wi反映的是经济损失（主目标）

• 第二部分 k 反映的是割边数量（辅目标）

因为 K>M≥k，所以任何两个割的比较，首先看的是 ∑wi 的大小（主目标优先）；只有当 ∑wi 相等时，才会比较 k 的大小（辅目标）。

3.4 K 应该取多大？

题目中 M≤1000，所以 K 取 1001 或更大的数即可。

• 如果 K=1001，那么任何两个最小割方案，只要损失差 ≥1，编码后的容量差就至少是 1001，远超边数差的最大值 1000，主目标一定优先。

• 跑完最大流后，ans / K 就是最小损失 C，ans % K 就是最少边数 T。

3.5 为什么是 +1 而不是 +0？

如果只乘 K 而不加 1，那么所有割的编码容量都是 K 的倍数，边数信息就丢失了。+1 的作用就是把边数编码进余数部分——每条被割的边贡献 1，总边数就是余数。

第四章：经典例题精解——洛谷 P1344 追查坏牛奶

4.1 题目呈现

题目来源：洛谷 P1344 [USACO4.4] 追查坏牛奶 Pollutant Control

题目描述：
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。你的任务是，在保证坏牛奶不送到零售商（仓库 N）的前提下，停止某些运输卡车，使损失最小。

输入格式：

• 第一行：两个整数 N(2≤N≤32)、M(0≤M≤1000)

• 第 22 到 M+1 行：每行三个整数 Si,Ei,Ci，表示从 Si到 Ei 的一条有向边，容量（停止损失）为 Ci

输出格式：

• 两个整数 C 和 T：C 表示最小的损失，T表示在损失最小的前提下，最少要停止的卡车数

输入样例：

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

输出样例：

60 1

4.2 建模分析

把每个仓库看作节点，每辆卡车看作一条有向边，边的容量就是停止这辆卡车的经济损失。

• 源点 s=1（发货工厂）

• 汇点 t=N（零售商）

目标是让 1 和 N 不连通，即找到一个割。最小割的容量就是最小的经济损失。

4.3 核心代码（C++17）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 35; // N <= 32
const int MAXM = 1005; // M <= 1000
const ll INF = 4e18;
const ll K = 1001; // 大于 M 的大数

struct Edge {
int to, rev;
ll cap;
};

vector<Edge> g[MAXN];
int level[MAXN], iter[MAXN];
int n, m;

// 添加一条有向边及其反向边
void add_edge(int from, int to, ll cap) {
g[from].push_back({to, (int)g[to].size(), cap});
g[to].push_back({from, (int)g[from].size() – 1, 0});
}

// BFS 构建层次图
bool bfs(int s, int t) {
memset(level, -1, sizeof(level));
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto &e : g[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
return level[t] >= 0;
}

// DFS 寻找增广路
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int &i = iter[v]; i < (int)g[v].size(); i++) {
Edge &e = g[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

// Dinic 最大流
ll max_flow(int s, int t) {
ll flow = 0;
while (bfs(s, t)) {
memset(iter, 0, sizeof(iter));
ll f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
// 核心技巧：边权编码为 w * K + 1
add_edge(u, v, w * K + 1);
}

ll ans = max_flow(1, n);
cout << ans / K << " " << ans % K << "\\n";
return 0;
}

4.4 代码详解

第34-36行：添加边时，容量设置为 w * K + 1。这就是核心的编码技巧。

第38-60行：标准Dinic算法。bfs 构建层次图，dfs 在层次图上寻找增广路。

第67-68行：跑完最大流后：

• ans / K 得到最小损失（主目标）

• ans % K 得到最少边数（辅目标）

4.5 样例验证

输入样例中，M=5M=5，K=1001K=1001。

各边编码后的容量：

• 1->3：100×1001+1=100101

• 3->2：50×1001+1=50051

• 2->4：60×1001+1=60061

• 1->2：40×1001+1=40041

• 2->3：80×1001+1=80081

跑最大流得到 ans=60061（割掉边 2->4，容量60，边数1）。

• C=60061/1001=60

• T=60061%1001=1

输出 60 1，与样例一致。

4.6 复杂度分析

• 时间复杂度：Dinic算法在一般图上的复杂度为 O(V^2E)。本题 V≤32，E≤1000，完全可行。

• 空间复杂度：O(V+E)。

4.7 另一种思路：两遍最大流

除了编码技巧，也可以分两次建图：

这种方法更直观，但需要跑两遍，代码量略大。编码技巧则一次建图、一次跑流，更加简洁高效。

总结

网络流最小割是算法竞赛中一个极其重要的模型。从“切断补给线”到“追查坏牛奶”，它的核心思想始终如一：用最小的代价，彻底阻断源点到汇点的所有通路。而最大流最小割定理则为我们提供了一个强大的工具——求最小割，就是求最大流。

P1344这道题的精髓在于多目标优化的处理技巧：当我们需要在“主目标最优”的前提下优化“辅目标”时，可以通过边权编码的方式，把两个目标合并到一条边的容量中，一次最大流同时解决两个问题。

三个关键点：

“最小割教会我们：有时候，解决问题的最佳方式不是找到最快的路，而是找到最便宜的‘断路’——切断，有时比连通更需要智慧。”

参考文献与延伸阅读