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}}; vectorint 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。如果数组只开 500RE 没商量。我的习惯是直接开到 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 这类题是有向图最小路径覆盖。二者分母容易混建议每次写之前先确认图的类型。另外一个小技巧是如果实在忘了定理可以直接从“匹配边带来多少个好处”入手推导。每多一条匹配边就少一个单点天线所以答案就是点数减匹配数。这个推导比硬记定理更可靠也不容易在考场上突然短路。