企业官网建设流程全解析

POJ3020 Antenna Placement 这道题，我最早是在刷二分图匹配专题时遇到的。当时第一眼看到题面“天线能覆盖一个城市，或者覆盖两个相邻城市”，第一反应是搜索或贪心，结果越想越复杂。后来搞明白它本质是最小边覆盖，再用最大匹配一算就通了。这篇从零开始拆解，把建图、定理、代码、踩坑一次讲透，适合刚刚接触二分图匹配的选手，也适合想彻底搞懂“为什么答案等于点数减匹配数”的人。

1. 题目模型与思路推导

1.1 题意还原

题目给一个 h 行 w 列的网格，里面每个格子要么是城市*，要么是空地o。现在要部署天线，一个天线有两种工作模式：

• 只覆盖一个城市；
• 覆盖两个上下左右相邻的城市（也就是用天线把这两个城市“串”起来）。

问最少需要多少个天线，才能把地图上所有城市都覆盖到。注意天线不能覆盖空地，两个被同一个天线覆盖的城市必须相邻，一个城市被一个天线覆盖即可，不需要重复覆盖。

这个模型本质上是：给定一张图，顶点是城市，边是“相邻关系”，每个天线可以选择覆盖一个顶点，或者选择一条边并覆盖该边的两个端点。目标是选最少的“边 + 点”组合，把全部顶点覆盖完。

1.2 从直觉到数学建模

先做一个最傻的方案：每个城市单独放一个天线，需要 N 个天线，N 是城市总数。问题马上就变成：把多少个“一个天线覆盖两个城市”的操作替换进来，可以省钱？

如果有一个天线覆盖两个相邻城市，那么相比两个天线分别覆盖它们，少用 1 个天线。能省多少，完全取决于有多少对城市可以这样两两配对。但这里有一个隐含限制：一个城市只能被一个天线覆盖，否则就浪费了。也就是说，这些“城市对”之间不能有共享城市。

此时问题已经清晰：城市是点，两个城市能用同一个天线覆盖等价于它们之间有一条边。我们要从图中挑出尽量多的边，且这些边两两不共享端点，这就是最大匹配。每找到一条匹配边，就比“每个城市单独一个天线”少用一个天线。因此答案就是：

最少天线数 = 城市总数 N - 最大匹配数 M

这个式子非常漂亮，但还有个关键问题：怎么保证剩下的点都能被单点天线覆盖？答案是肯定的，因为单点天线无条件可用。所以最优化目标就是让匹配边数量最大。

2. 二分图匹配与最小边覆盖的数学内核

2.1 为什么一定是二分图

很多初学者会想：这个图不是任意图吗？城市之间只要有边，都可以建模成一般图的最大匹配。理论上是这样，但竞赛里求一般图最大匹配要用到带花树算法，实现复杂，而且这个题根本不需要。

注意到网格天然是二分图。对任意格子(i, j)，定义它属于集合 A 当且仅当(i + j) % 2 == 0，否则属于集合 B。上下左右移动一格，奇偶性必然改变，所以相邻城市的颜色一定不同。城市子图保留了网格的二分性质，所以我们可以把 A 类城市当作二分图左部，B 类城市当作右部，只从 A 连向 B。

2.2 最小边覆盖定理

在无孤立点的图 G 中，最小边覆盖数等于|V| - 最大匹配数。这里的“边覆盖”指选择若干条边，使每个顶点至少与其中一条边关联。本题更特殊：天线覆盖单个城市等价于允许“点覆盖”，所以即使有孤立点也不影响结论，因为孤立点不参与匹配，直接单点覆盖即可。

证明思路可以这样理解。任取一个最大匹配 M，它覆盖了 2|M| 个顶点。剩下N - 2|M|个顶点之间一定没有边，否则就能把这条边加入匹配，和 M 的最大性矛盾。于是这些顶点每个只能单独用一个天线覆盖。总天线数就是：

|M| + (N - 2|M|) = N - |M|

反过来看，任何一组覆盖方案里，假设有 k 个天线覆盖了两个城市，这 k 个天线对应的城市对在图中构成一个匹配，所以 k 不可能超过最大匹配数 M。因此方案数至少是N - k >= N - M。两边夹住，结论就成立了。

2.3 最大匹配算法选型

二分图最大匹配的标准算法是匈牙利算法，复杂度 O(VE)。本题最多 40×40 个格子，就算全是城市也只有 1600 个点，边数也不会超过 4×1600/2，完全够用。

比起最大流等算法，匈牙利算法对这道题还有一个优势：代码短、递归直观、方便调 bug。这也是很多老题解普遍采用它的原因。

3. 建图细节与匈牙利算法完整实现

3.1 城市编号与黑白染色

建图第一步是给每个城市一个编号。我用一个id[i][j]数组保存“坐标到编号”的映射，同时用两个辅助数组记录编号对应的坐标，方便后面判断颜色。

int id[45][45]; int px[2005]; // 编号对应的行 int py[2005]; // 编号对应的列 for (int i = 0; i < h; ++i) { scanf("%s", mp[i]); for (int j = 0; j < w; ++j) { if (mp[i][j] == '*') { id[i][j] = ++tot; px[tot] = i; py[tot] = j; } } }

接下来遍历所有城市，如果(i + j) % 2 == 0，它作为左部节点。检查它的四个方向，如果也是城市，就把右部城市编号加入左部节点的邻接表。

注意这里只从黑色格子向白色格子连边，这样不会重复建边，也保证匹配边对应原图的一条边。

int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (mp[i][j] == '*' && ((i + j) & 1) == 0) { int u = id[i][j]; for (int d = 0; d < 4; ++d) { int ni = i + dirs[d][0]; int nj = j + dirs[d][1]; if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue; if (mp[ni][nj] == '*') { int v = id[ni][nj]; G[u].push_back(v); } } } } }

3.2 匈牙利算法模板

匈牙利算法的核心是递归增广。matchR[v]表示右部节点 v 当前匹配的左部节点编号，vis用于一次增广过程中防止重复访问。

bool dfs(int u) { for (int v : G[u]) { if (vis[v]) continue; vis[v] = true; if (matchR[v] == -1 || dfs(matchR[v])) { matchR[v] = u; return true; } } return false; }

主流程里，对所有左部节点做一次 dfs，累加成功的次数就是最大匹配数。每次 dfs 前都要把vis清零。

int maxMatch = 0; memset(matchR, -1, sizeof(matchR)); for (int u = 1; u <= tot; ++u) { if (((px[u] + py[u]) & 1) != 0) continue; // 只从左部发起增广 memset(vis, false, sizeof(vis)); if (dfs(u)) ++maxMatch; } int ans = tot - maxMatch; printf("Case %d: %d\n", cas, ans);

3.3 完整代码

#include <cstdio> #include <cstring> #include <vector> using namespace std; const int MAXN = 2005; int T, h, w; char mp[45][45]; int id[45][45]; int px[MAXN], py[MAXN]; int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; vector<int> G[MAXN]; int matchR[MAXN]; bool vis[MAXN]; bool dfs(int u) { for (int v : G[u]) { if (vis[v]) continue; vis[v] = true; if (matchR[v] == -1 || dfs(matchR[v])) { matchR[v] = u; return true; } } return false; } int main() { scanf("%d", &T); for (int cas = 1; cas <= T; ++cas) { scanf("%d%d", &h, &w); int tot = 0; for (int i = 0; i < h; ++i) { scanf("%s", mp[i]); for (int j = 0; j < w; ++j) { if (mp[i][j] == '*') { id[i][j] = ++tot; px[tot] = i; py[tot] = j; } } } for (int i = 1; i <= tot; ++i) G[i].clear(); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (mp[i][j] == '*' && ((i + j) & 1) == 0) { int u = id[i][j]; for (int d = 0; d < 4; ++d) { int ni = i + dirs[d][0]; int nj = j + dirs[d][1]; if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue; if (mp[ni][nj] == '*') { int v = id[ni][nj]; G[u].push_back(v); } } } } } int maxMatch = 0; memset(matchR, -1, sizeof(matchR)); for (int u = 1; u <= tot; ++u) { if (((px[u] + py[u]) & 1) != 0) continue; memset(vis, false, sizeof(vis)); if (dfs(u)) ++maxMatch; } printf("Case %d: %d\n", cas, tot - maxMatch); } return 0; }

4. 调试实录：常见失误与优化技巧

4.1 经典误区：拆点后除以 2

网上有不少题解会把每个城市拆成两个节点，分别放在左右两部，然后对每个相邻关系添加两条有向边，跑完最大匹配后除以 2。这种做法本身可以 AC，但非常容易踩坑，尤其是在注释不清的代码里，新人看到“除以 2”会一头雾水。

我强烈建议直接用网格染色建图。这样做有几个好处：

• 每条边只添加一次，匹配数不会翻倍；
• 建图代码的意图一目了然；
• 不需要额外处理“重复边”带来的倍增干扰。

如果你确实想理解拆点版，一句话就能说清：因为一条无向边被拆成了两个方向，原图的一条匹配边在拆点二分图里会对应两条匹配边，所以最后要除以 2。但要真正理解这件事，还是要把“二分图匹配的边必须对应原图一条边”这件事想透，否则一改数据就容易出错。

4.2 按编号奇偶性建边是否可靠

我第一次写这题的时候，想偷懒，不按(i + j)判断颜色，而是按城市编号的奇偶性分左右。实测在某些数据下是错的。原因是编号是按照行优先顺序递增的，上下相邻的两个城市，如果列数 w 是奇数，编号奇偶性可能相同，也可能不同；左右相邻的城市编号奇偶性一定相反。也就是说，编号奇偶性不能保证相邻城市分属两部。

所以最稳妥的方案永远是记录坐标，用(px[u] + py[u]) % 2判定颜色。这也是我重建数组记录坐标的原因。

4.3 城市数量上限与数组大小

POJ3020 的网格尺寸是 40×40，最极端情况全是城市，总数 1600。如果数组只开 500，RE 没商量。我的习惯是直接开到 2005，给编号数组留余量。id[45][45]也要小心，不要顺手开成40，下标会越界。

还有一点，matchR和vis的长度必须按右部节点编号上限来开。城市编号是 1..tot，所以开到 MAXN 即可。很多人因为左部右部都想用同一个数组，结果 memset 时越界，这种错误在 OJ 上报错还不明显，会变成神秘 RE。

4.4 递归深度与复杂度

匈牙利算法的递归深度不超过右部节点数量，最多 1600 层，不用担心栈溢出。时间复杂度 O(VE)，这里 V 是二分图的左部节点数，E 是边的数量。最坏情况下 E 约为 2×1600，整体完全可以在题目限制内跑完。

我实测过一个 40×40 全*的极端用例，本地运行时间几乎为 0。这个规模的根本不用想优化，直接暴力匈牙利就好。如果你在别的题里遇到点数上万，那就需要用到 Hopcroft-Karp 算法，但那是后话了。

4.5 一个方便验证的小样例

自己测的时候我最常跑的一组数据是：

1 2 2 ** **

4 个城市两两相邻。黑点有两个，每个都连两个白点，最大匹配为 2，答案等于4 - 2 = 2。也就是说，两根天线斜着或水平垂直交叉配对都行。如果答案是 1，那说明建图或者匹配算错了。

再试单行三个城市：

1 1 3 ***

三个城市连成一条线，最大匹配是 1，答案3 - 1 = 2。这个用例能帮你区分“最大匹配”和“直觉配对”的区别：别以为 3 个点能配出 2 对，匹配边不能共享端点，所以最多只有 1 对。

5. 总结之外的一些提醒

这道题真正的价值，不是让你背会一个匈牙利模板，而是让你建立“问题到模型”的转化直觉。看到“每个天线覆盖一个点或两个相邻点”，立刻要想到边覆盖；想到边覆盖，立刻要想到最大匹配；再看到网格，立刻要想到棋盘染色二分图。这条链路里任何一环断了，就会绕到搜索去，复杂度直接爆炸。

我自己后来做题时，遇到很多类似问题，比如无向图用最小路径覆盖、有向 DAG 用最小路径覆盖，都和点数 - 最大匹配有关。但它们的区别一定要分清楚：本题是无向图的点覆盖变体，而 HDU1151 这类题是有向图最小路径覆盖。二者分母容易混，建议每次写之前先确认图的类型。

另外一个小技巧是：如果实在忘了定理，可以直接从“匹配边带来多少个好处”入手推导。每多一条匹配边，就少一个单点天线，所以答案就是点数减匹配数。这个推导比硬记定理更可靠，也不容易在考场上突然短路。