企业官网建设流程全解析

看到 P2057 这个编号，很多同学第一反应是数据结构、并查集或者贪心，结果点开题解满屏都是最大流最小割，直接傻眼。作为一道同时出现在两届省选里的经典题（[SHOI2007]善意的投票 和 [JLOI2010]冠军调查，题目内容完全一致），P2057 几乎可以算国内选手系统学习"二元标记最小割"模型的必修课。

这题最大的特点就是：题意直白、数据范围小、代码也不长，难点全在"怎么把文字翻译成图"这一步。如果你能独立完成这个翻译，后面再遇到一大票"二选一 + 冲突代价"的优化问题，都会觉得似曾相识。这篇文章我就从题意拆解开始，把建模过程、代码实现、易错细节，以及这个模型能迁移到哪些场景，完完整整过一遍。

1. 题目到底在说什么：先拆掉"投票"的包装

1.1 抽掉场景之后，问题长这样

用"善意的投票"这版来表述：有 n 个人，每个人心里已经有一个初始意愿，不是 0 就是 1。他们之间有 m 对朋友关系。现在每个人都要给出一个最终表态，最终表态可以和初始意愿不同，但不能白改，每改一次产生 1 点代价；如果两个互为朋友的人最终表态不一样，也会产生冲突，每对冲突产生 1 点代价。问最小总代价是多少。

"冠军调查"那版把 0/1 换成了"认为某队是冠军 / 认为某队不是冠军"，本质完全一样。这类题喜欢套一个生活场景，但抽掉场景就是：n 个点，每个点要贴一个 0/1 标签，贴错标签有单点代价，相邻点标签不同有边代价，求最小总代价。

第一次见这题，很多人会觉得"这不就是并查集吗"或者"跑个二分图染色？"但实际上，图是任意的，不是树也不是二分图，所以树形 DP 和染色都不好使。还有人说用 2-SAT，但 2-SAT 只回答"有没有可行方案"，这题要的是带权最小化，而且允许付代价来改变意愿，这正好是网络流割模型最擅长的场景。

1.2 最小割凭什么能解决"每个人做决定"的问题

一句话：最小割就是"用最少的代价把图切开"，而"把图切开"恰恰对应着"给所有人做最终决定"的过程。

具体来说，我们建立一个源点 S 和一个汇点 T。跑完最小割后，整个图被切成两部分：和 S 连通的那部分，我们规定为"最终选择 1"的人；和 T 连通的那部分，规定为"最终选择 0"的人。那么一个人最终选什么，只看他最后在哪个集合里。

代价全部变成"割边"：

• 一个人改变了初始意愿，对应着他和初始意愿那一侧的联系边被切断；
• 一对朋友意见不一致，对应着他们之间那条连接边被切断。

这样原问题就变成一个最小割问题。而最小割数值等于最大流数值，所以我们只需要建图之后跑一遍最大流，直接输出答案。这是全题最核心的思维跳跃：把"选择"重新解释成"分割后的归属"，把"代价"统一解释成"被切掉的边"。这一步想通了，题目就做出来一半了。

2. 建模细节：三个关键决策背后的为什么

2.1 源点连谁、汇点连谁，容量为什么是 1

先给出标准建图，再逐条解释。

// S 表示"最终选择 1"，T 表示"最终选择 0" for (int i = 1; i <= n; i++) { int v; cin >> v; if (v == 1) addEdge(S, i, 1); else addEdge(i, T, 1); }

初始意愿为 1 的人，从 S 向他连一条容量 1 的边；初始意愿为 0 的人，从他向 T 连一条容量 1 的边。

为什么容量是 1 而不是无穷大？因为题目里"改变意愿"的代价就是 1。你想让改票代价变成多少，就把容量设成多少。用 INF 等于告诉程序"改票这件事根本不允许"，答案就会严重偏大。

再从割的角度看一遍：如果某人的最终归属和他初始意愿相同，那么这条与 S 或 T 相连的边两头在同一个集合里，不会被割到；如果最终归属变了，这条边就会横跨两个集合，必然被割掉，容量 1 计入最小割。这一组边的任务就是为"改变意愿"定价。

2.2 朋友之间为什么要加双向边，而且容量也是 1

朋友关系的处理是这道题里最容易理解错的地方：

for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; addEdge(u, v, 1); addEdge(v, u, 1); }

有人会问：两个人意见不同就冲突 1 次，那加一条容量 1 的边不就行了？在算法题实现里，没有真正的无向边，你要么拆成两条有向边，要么手动加两个方向的边。

为什么必须两个方向都加？因为最终割的时候，如果 u 在 S 侧、v 在 T 侧，被割到的是 u→v 这条边；反过来，如果 u 在 T 侧、v 在 S 侧，被割到的是 v→u 这条边。只加一个方向，就只覆盖了"u 选 1、v 选 0"这一种情况，另一种方向就漏掉了。

加两条有向边之后，不管两个人最终谁选哪边，只要他们不在同一侧，就会恰好有一条"从 S 侧指向 T 侧"的边被割掉，代价正好是 1。如果他们同边，两个方向都不会被割，代价 0。

生活里很好类比：两个人吵架，A 选 1、B 选 0，矛盾是 1；A 选 0、B 选 1，矛盾还是 1。方向只是建模时加进去的"箭头"，冲突本身是对称的，所以必须双向都加。

这里还有一个很多人会犯的直觉错误：觉得朋友之间应该用 INF 容量，表达"朋友关系不能破裂"。千万别这么干。题目说的是"有矛盾就有代价，代价是 1"，这不是硬性约束。容量多大，代价就是多大，把容量调成 INF，等于强行禁止一切跨阵营的朋友关系，答案自然不对。

2.3 为什么跑出来的最大流就是答案

建完图之后，最小割的值就是答案，而由于最大流等于最小割，我们只要跑一遍最大流算法，直接输出 flow 就是答案。

我第一次做这题的时候，卡在"答案为什么是 flow"这里很久。后来想明白：flow 本身没有任何直观意义，它只是一个用来计算最小割数值的工具数值。重要的不是"流量"怎么流过去，而是"最小割的容量是多少"。最大流算法只是求解最小割的高效工具，你完全可以把输出值理解为"最小割的容量"，而不是"流量"。

打个比方，你问路时别人告诉你"朝东走 500 米到"，"500 米"这数字本身没意义，有意义的是它帮你找到了目的地。最大流就是那个"500 米"。

2.4 跑完还能输出方案：割的可视化

如果题目要求输出每个人最终选什么，也就是要方案，可以在跑完最大流之后顺手拿。方法是从 S 出发，沿着残量网络中 cap > 0 的边做一遍 DFS，所有能走到的点都在 S 侧，表示最终选 1；走不到的就是 T 侧，表示最终选 0。

这一步在 P2057 里用不到，但很多输出方案的最小割题是标配。我强烈建议你写完代码后，加一段调试逻辑：输出"哪些人改了票、哪些朋友产生了冲突"。改票人数和冲突对数加起来，应该正好等于答案。这个验证方法能帮你发现建模方向有没有搞反，比对着样例空想靠谱得多。

3. 完整实现：一个可以直接 AC 的 Dinic 模板

3.1 整体结构

这题 n 和 m 的规模都在几百的量级，Dinic 跑起来非常快。我习惯用 vector 存边，因为省心，不会像数组式邻接表那样动不动越界。给出一份完整可用的代码框架：

#include <bits/stdc++.h> using namespace std; const int MAXN = 505; const int INF = 0x3f3f3f3f; struct Edge { int to, cap, rev; }; vector<Edge> g[MAXN]; int level[MAXN], iter[MAXN]; void addEdge(int u, int v, int c) { g[u].push_back({v, c, (int)g[v].size()}); g[v].push_back({u, 0, (int)g[u].size() - 1}); } bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queue<int> q; level[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (auto &e : g[u]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[u] + 1; q.push(e.to); } } } return level[t] >= 0; } int dfs(int u, int t, int f) { if (u == t) return f; for (int &i = iter[u]; i < (int)g[u].size(); i++) { Edge &e = g[u][i]; if (e.cap > 0 && level[e.to] == level[u] + 1) { int 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; } int maxFlow(int s, int t) { int flow = 0; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); int f; while ((f = dfs(s, t, INF)) > 0) flow += f; } return flow; } int main() { int n, m; cin >> n >> m; int S = 0, T = n + 1; for (int i = 1; i <= n; i++) { int v; cin >> v; if (v == 1) addEdge(S, i, 1); else addEdge(i, T, 1); } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; addEdge(u, v, 1); addEdge(v, u, 1); } cout << maxFlow(S, T) << endl; return 0; }

3.2 代码里容易忽略的细节

第一，addEdge 内部的反向边容量为 0，这是网络流的标准姿势。反向边的作用是给算法"反悔"的机会，它的容量表示"还能退还多少流量"，初始当然是 0，不要自作主张改成 1。

第二，朋友边要调用两次 addEdge。调用一次只加了"u→v"方向容量 1，自动生成的反向边容量是 0，这不足以表达对称冲突。很多新手误以为自动生成的反向边就是另一个方向，其实那是给最大流"退流"用的，不是给题目"另一种冲突方向"用的。

第三，dfs 里的层数判断写成level[e.to] == level[u] + 1，这是 Dinic 的标准写法，严谨而且不容易出奇怪问题。

第四，因为朋友关系拆成了两条有向边，实际总边数是 2 * (n + 2m) 条（每条 addEdge 内部产生正反两条）。如果改用数组式邻接表，记得开够 2 * (n + 2m) 以上。很多人第一次就在这里 RE。

3.3 为什么选 Dinic 而不是 EK 或 ISAP

数据范围摆在那里，EK 其实也能过，几百个点、几百条边，最坏情况差不了多少。但从学习角度，我建议直接上 Dinic，因为后面很多最小割题的数据范围会更大，EK 容易被卡，而 Dinic 在分层图、二分图上的表现都稳定，是一个通吃大多数题型的模板。

ISAP 也可以，常数更小，但引入 gap 优化、当前弧优化一大堆概念，对新手不友好。做题先求稳，Dinic 够用了。如果你以后打比赛发现 Dinic 被卡，再学 ISAP 也不迟。

3.4 输入输出注意

题目输入是先 n 后 m，然后 n 个 0/1 表示每个人的初始意愿，再 m 行每行两个数表示朋友关系。读的时候别搞反。输出是一个整数，表示最小总代价。代码里 S 取 0、T 取 n + 1，是因为人的编号从 1 到 n，这样源点和汇点不会和任何人冲突。

4. 实战中我踩过的坑：问题排查实录

4.1 RE：边数组开小了

如果不用 vector，而是用数组式邻接表：

struct Edge { int to, cap, next; } e[MAXE]; int head[MAXN], cnt;

addEdge 函数里 cnt 交替加正反两条边。总边数不是 m，也不是 n + m，而是 2 * (n + 2m)。所以 MAXE 至少要开到 2 * (n + 2m) + 5。

很多人按 n + m 开，小数据没事，一到大数据就 RE，或者更隐蔽——不 RE 但答案错。vector 版本能彻底避免这个问题，我建议新手一律用 vector。

4.2 WA：朋友边只加了一个方向

我有一次复制代码改题，addEdge(u, v, 1) 写完后想着"反边 addEdge 里面已经自动生成了啊"，就漏了 addEdge(v, u, 1)。结果样例都过不了。这个"反边自动生成"的想法是对的，但自动生成的是容量 0 的反向边，不是容量 1 的另一个方向。朋友关系必须手动加两条容量 1 的边。

4.3 WA：把源点连边方向搞反

有人会习惯"所有人向 S/T 各连一条边"，其实每个人只需要往一侧连：初始意愿 1 的人连 S，初始意愿 0 的人连 T。如果每个人同时连 S 和 T，容量又都是 1，那么最小割就变成了"对每个人至少付 1"，答案必然偏大。

正确的直觉是：每个人都天生站在自己初始意愿那一边，不需要付出任何代价就可以保留初始选择。那条"S 到他的边"不是奖励，而是"如果他不选初始意愿，就要剪断这条边付代价"。

4.4 为什么有时候看到题解说答案是 n - flow

有些题解里会出现 n - flow 的写法，原因是他们采用了另一种建图：源点向所有人连容量 1，表示"默认全选 1"，然后通过收益函数做转化。那种建法把两个选项设计成不对称的收益模型，最后用总收益减最小割，就会得到 n - flow。但如果你用我上面这种"代价式"对称建图，答案直接就是 maxFlow，不需要再做减法。

我的建议是，认准一种语义清晰的建图，不要混合记忆。想验证自己的图建得对不对，就跑完最大流后输出一下最小割的 S 侧集合，手动检查每个割边对应的实际代价，如果全对得上，答案基本就稳了。

5. 从一道题到一类题：二元标记最小割的通用套路

5.1 模型的骨架

P2057 属于一个非常通用的建模家族：二元标记最小割。这个家族的题目都有一个统一骨架：

• 每个元素对应一个节点，最终状态只有两个选项，映射为 S 侧或 T 侧；
• 如果某个元素选择某一方有额外代价，就从该节点向 S 或 T 连一条边，容量就是代价；
• 如果某两个元素的"选择组合"会带来代价，就用一条边连接两个节点，容量取决于代价函数；
• 最小割容量就是最小总代价。

在这个框架下，P2057 是"选择不同的惩罚为 1"的最简单例子。稍微扩展一点，还能处理更复杂的代价表，比如"两个都选 1 有收益，两个都选 0 有收益，一个选 1 一个选 0 有惩罚"，方法是通过拆点或者加辅助点把收益转换成惩罚，最终都变成割边容量。这就是最大权闭合子图模型的套路。

5.2 能迁移的真实场景

我见过很多问题都是这个模型的套壳。

第一类是网格图上的区域分割问题。比如有一片区域，每个格子选"开发"还是"保留"都有各自的收益，相邻格子如果属性不同会造成环境冲突损失。把地图上的相邻关系变成边，把冲突损失变成容量，跑一次最小割就能得到最优划分。原理和 P2057 完全一致，只是点多了、边多了。

第二类是比赛分组类问题。若干队伍、若干场比赛，要求把每支队伍分进"候选"或"非候选"两个集合，如果有互相看好的队伍被分到不同集合，就会产生宣传成本。这其实就是把"冠军调查"里的人换成队伍，朋友关系换成某种互相影响关系。

第三类是机器学习里的图像分割。像素点要分成前景和背景，每个像素有属于前景/背景的不同概率，对应 S/T 边的容量；相邻像素如果被分到不同类别，产生平滑惩罚，对应节点之间的边容量。整个模型就是最朴素的图割算法，P2057 就是它的玩具版。这也是为什么我说这道题值得认真学——它不是一道孤立的 OI 题，而是很多领域里真实在用的基础模型。

5.3 一个容易写成错误的变形

如果题目变成"最大化收益"而不是"最小化代价"，很多新手会直接改边容量然后跑最大流，这是不对的。正确做法是先把所有正收益加起来，把所有负收益、惩罚都变成割边容量，然后最大收益 = 总收益 - 最小割。这是最大权闭合子图模型的套路。

P2057 之所以是个好的入门题，就是因为它没有"总收益 - 最小割"这层转换，把所有代价直接放在边容量上，答案就是最小割，干净利落。等你把这个模型吃透了，再去看那些收益和惩罚混合的题，思路会顺很多，至少不会被"到底连 S 还是连 T、容量设多少"这种问题反复折磨。

我自己当年第一次写这题，最小割建图折腾了整整一个晚上。最玄妙的一刻是当我用最大流模板跑出答案，再手动枚举一个小例子的所有方案，发现 flow 的值和我手动算出的最小代价完全一致。那一刻我才真正理解"最小割就是最小代价"这句话的分量。

如果你现在正被这题卡住，我的建议是：别急着看题解代码，先拿纸画一个 n=3、m=2 的小例子，手动枚举每人的两种选择，算一算每种方案的总代价，然后对照建图，看每一种方案对应哪种割法，代价是不是一一对上。这个过程只需要半小时，但比看十篇题解都管用。

建图这种事，看懂了是别人的，亲手推一遍才是自己的。