1. 先把题意嚼碎了再谈算法
1.1 题目在问什么
POJ 3020 的 Antenna Placement，题面读起来像一道小模拟：给你一个 h × w 的网格，格子里要么是*代表城市，要么是o代表空地。你手里有一种天线，这种天线有两种用法：单独覆盖一个城市，或者同时覆盖两个上下左右相邻的城市。问最少需要多少个天线，才能把网格里所有城市都覆盖到。
输入是 T 组数据，每组先给 h 和 w，然后给 h 行字符串。这里有两个隐含约束很多人会忽略：一是天线不能斜着覆盖，二是天线的"覆盖两个城市"必须是一对相邻城市，不能隔着一个城市去覆盖远处。换句话说，如果两个城市之间没有公共边，它们就没法共用一个天线。
我第一次看到这题的时候，第一反应是：这不就是尽量把相邻的城市两两配对嘛，配得越多，省的天线越多。这想法方向是对的，但"尽量配对"这四个字没那么简单。城市之间的相邻关系是互相纠缠的，你在这个位置配了一对，可能就把另外三对能配的全部堵死了。所以这题的本质是一个组合优化问题，不是看一眼局部就能贪出来的。
1.2 为什么不能简单贪心
举个最典型的例子：一个十字星形状的城市群，中间一个城市，上下左右各一个城市。中间那个城市和四个方向的城市都相邻，但四个方向的城市彼此之间不相邻。这时候你最多只能让中间城市和其中一个方向配对，剩下的三个方向全都只能单独覆盖。一眼看过去可能觉得"那我让中间的和左边配，三个单独覆盖，总共 4 个天线"，但如果你让中间的和上方配，下方、左方、右方三个单独覆盖，也还是 4 个。怎么选都是 4 个，因为核心约束在于中间城市只能配一次。
再想深一层：如果把城市看成点，相邻关系看成边，那"让一对相邻城市共用一个天线"就是"选一条边"。两个天线不能覆盖同一个城市，等价于选出来的边不能共用一个端点。这不就是图论里的匹配吗？所以题目真正的图论模型是：在"城市相邻图"里找一个最大的匹配，然后用"总城市数 − 匹配数"作为答案。这个结论我后面会详细推导，但你现在可以先记住：这题不是让你去贪心，而是让你在所有可能的配对方案里，找出一组数量最多、又互不冲突的配对。
2. 从网格到二分图：棋盘染色是关键一步
2.1 城市是点、相邻是边
先把问题抽象成图。每个*城市是一个顶点，如果两个城市在网格里上下左右相邻，就在它们之间连一条无向边。这样我们就得到了一个城市相邻图 G。
在这个图里，一个覆盖两个相邻城市的天线对应一条边，一个只覆盖单个城市的天线对应一个"单点"。我们的目标是用最少的"边 + 单点"覆盖住所有顶点。假设图里最多能找到 m 条互不共享端点的边，也就是最大匹配的大小为 m，那么这 m 条边覆盖了 2m 个城市，用了 m 个天线。剩下 n − 2m 个城市没有被匹配覆盖到，每个城市只能单独用一个天线。总天线数就是：
m + (n − 2m) = n − m
所以最小天线数 = 城市总数 − 最大匹配数。这个公式是整个题目的灵魂，但很多人只是背下来，并不知道它为什么成立，也不知道它成立的前提是什么。我后面专门用一节来讲这个推导。
2.2 网格图天然是二分图
现在问题来了：求最大匹配本身是好做的，匈牙利算法也好、匈牙利算法的优化版也好，都能搞定。但前提是图必须是二分图。城市相邻图是二分图吗？
答案是肯定的，而且原因非常漂亮：给每个格子标一个"奇偶染色"，把坐标 (i, j) 的 i + j 的奇偶性作为颜色。你从任何一个格子走到上下左右的相邻格子，i + j 的值要么加一要么减一，奇偶性一定翻转。也就是说，网格里所有边都是连接"偶格点"和"奇格点"的，不存在任何一条边连接两个同色格子。
这意味着，不管你网格里面有多少城市、城市的分布有多乱，只要它们通过"上下左右相邻"这一规则连边，整张图就一定是二分图。把 i + j 为偶数的城市归为左部，把 i + j 为奇数的城市归为右部，所有边都是从左部指向右部（或者反过来）。这是网格图最优雅的性质之一，也是这题能用二分图匹配的根本原因。
2.3 为什么不能用行号或列号拆分
我见过有同学想当然地用"行号奇偶"或者"列号奇偶"来拆左右部，这会在某些数据上直接翻车。比如一个横向相邻的格子对，它们的行号相同，如果用行号奇偶拆分，两个城市会被分到同一部，这样就出现了"同部边"，二分图匹配算法就跑不了了。
只有 (i + j) 的奇偶性才是网格相邻关系的天然二部划分，因为每次移动一步，i 和 j 中恰好有一个变化 1，总和奇偶性必然翻转。这也提醒我们：建模的时候不要凭感觉选划分方式，要看连边规则到底是什么。连边规则是"上下左右距离为 1"，那就用曼哈顿距离奇偶性来划分。
3. 建图细节与匈牙利算法完整实现
3.1 给城市编号，避免直接用坐标当顶点
匹配算法的代码里要用一维整数来代表顶点，所以第一步是把二维网格里的每个*映射成一个编号。做法是开一个和网格同样大小的 int 数组 id，扫描整个网格，每当遇到一个*，就把计数器加一，然后把计数器值存在对应的 id[i][j] 里。注意这里所有城市共用一个编号池，偶部奇部共用 1 到 cnt 这一套编号，不要分两套，否则匹配数组的下标会乱。
建边的时候，对每个城市枚举它的四个方向邻居。如果邻居也是*，说明这两个城市之间有一条"可以共用一个天线"的候选边。这里有个去重技巧：因为每条无向边会被两个端点各枚举一遍，如果你不加控制，邻接表里会出现两条方向相反的重复边。重复边不影响正确性，但会影响效率，更重要的是容易让你在调试的时候看晕。我的习惯是：统一把边建成"偶部指向奇部"。具体做法：遍历每个城市 u，如果 u 的 (i + j) 是偶数，就把奇部邻居 v 加到 g[u] 里；如果 u 是奇部，就反过来把 u 加到 g[v] 里。这样每条边只存一次，方向永远是偶到奇。
3.2 完整代码（C++）
这里给出我常用的写法，匈牙利算法用最经典的 DFS 增广路版本，注释写得比较细：
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int MAXN = 405; // 城市数上限约 400 int h, w; char mp[45][45]; // 原网格 int id[45][45]; // 坐标 -> 城市编号 vector<int> g[MAXN]; // 邻接表，统一左部(偶) -> 右部(奇) int match[MAXN]; // match[v] = 右部顶点 v 匹配的左部顶点 bool vis[MAXN]; // 每次 dfs 的访问标记 // 从左部顶点 u 出发找增广路 bool dfs(int u) { for (int v : g[u]) { if (vis[v]) continue; vis[v] = true; if (match[v] == -1 || dfs(match[v])) { match[v] = u; return true; } } return false; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &h, &w); for (int i = 0; i < h; i++) scanf("%s", mp[i]); int cnt = 0; memset(id, 0, sizeof(id)); for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (mp[i][j] == '*') id[i][j] = ++cnt; for (int i = 1; i <= cnt; i++) g[i].clear(); vector<int> left; // 偶部顶点集合 int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (mp[i][j] != '*') continue; int u = id[i][j]; if (((i + j) & 1) == 0) left.push_back(u); // 偶部 for (int k = 0; k < 4; k++) { int ni = i + dx[k]; int nj = j + dy[k]; if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue; if (mp[ni][nj] != '*') continue; int v = id[ni][nj]; // 统一存成 偶 -> 奇 if (((i + j) & 1) == 0) g[u].push_back(v); else g[v].push_back(u); } } } memset(match, -1, sizeof(match)); int matching = 0; for (int u : left) { // 只从左部开始找增广路 memset(vis, 0, sizeof(vis)); if (dfs(u)) matching++; } printf("%d\n", cnt - matching); // 答案 = 城市数 - 最大匹配 } return 0; }3.3 复杂度分析
匈牙利算法的复杂度是 O(VE)，这里的 V 是城市数，上限约 400；每个城市的出边最多 4 条，所以 E 的上限也就 1600 左右。V × E 撑死了 64 万，跑多少组数据都没压力。就算你做得更暴力一点，每个点把四个方向都推一遍，也完全不会超时。这题对算法复杂度非常宽容，真正的难点在建模，不在优化。
有同学可能会想：要不要上 Hopcroft-Karp？没必要，匈牙利在这个数据量下已经够了。但如果你把 id 数组开到 1600、或者网格再大一点，匈牙利依然是可接受的，因为哪怕是 1600 个点、6400 条边，也不过一千万级别的操作量。当然，追求稳妥的话，把 MAXN 开大一点也没坏处，我习惯开到 1605 省得边界出问题。
4. 答案为什么是"点数 − 最大匹配"
4.1 一步一步把公式推出来
最小天线数 = 城市数 − 最大匹配数，这个公式在题解里出现频率很高，但很多人没真正理解。我换个角度重新推一遍。
假设我们在城市相邻图里取了一个匹配 M，大小为 m。这 m 条匹配边对应 m 个天线，每个天线覆盖了这条边两端的两个城市，共覆盖 2m 个城市。剩下的 n − 2m 个城市，因为和任何已覆盖城市都不能再共用天线，只能各用一个天线。于是总天线数 = m + (n − 2m) = n − m。显然，m 越大，总天线数越小，所以答案就是 n − 最大匹配数。
那为什么"剩下的城市各用一个天线"一定可行？因为题目允许天线单独覆盖一个城市，所以哪怕某个城市周围全是空地、一个邻居都没有，它也能被一个单点天线覆盖。这就避开了图论里"最小边覆盖需要图中无孤立点"的那个前提限制，让公式变得无条件成立。
4.2 最小边覆盖跟这个公式是什么关系
如果你学过图论里的边覆盖，会发现这正是"最小边覆盖 = 顶点数 − 最大匹配"这个定理的具体应用。严格证明分两步：
第一步，任意最大匹配大小为 m，按上面的构造能得到一个大小为 n − m 的边覆盖，所以最小边覆盖 ≤ n − m。
第二步，反过来看，任意一个边覆盖如果有 c 条边，取其中所有边构成子图。因为这是最小边覆盖，每条边至少有一个端点在子图里的度是 1，否则把这条边删掉，两个端点依然被其他边覆盖，覆盖数会更小。也就是说，这个子图里每个连通分量都是"星形"结构：一个中心点挂着若干叶子。一个包含 r 个顶点、s 条边的星形分量，满足 s = r − 1，同时它内部的最大匹配是 1 = r − s。把所有分量加起来，就能从覆盖里抽出大小为 n − c 的匹配。所以最大匹配 ≥ n − c，即最小边覆盖 ≥ n − 最大匹配。两边一夹，定理成立。
这题本质上就是在城市相邻图上求最小边覆盖，只不过允许用"单点天线"来覆盖孤立点，所以不用额外特判。
4.3 千万别和"最小路径覆盖"混在一起
图论题里还有一个非常常见、长得几乎一模一样的公式：DAG 的最小路径覆盖 = 顶点数 − 最大匹配。很多人看到"顶点数减匹配数"就条件反射地套路径覆盖模板，把每个点拆成入点和出点，然后发现答案对不上，整个人就懵了。
区分它们的核心看两点：第一，路径覆盖问题要求拆点，因为一个点可能既是前一条路径的末尾又是后一条路径的开头，需要通过拆点来限制每个点只能被覆盖一次；而边覆盖问题不拆点，因为我们要选的只是一组互不共享端点的边。第二，路径覆盖里的"边"表示路径上的一条衔接关系，要求图是有向的、无环的；而这里的边就是城市之间的相邻覆盖关系，是天然无向的。
一句话总结：看到"点数减匹配"别急着抄模板，先想清楚这个匹配到底匹配的是什么。在 POJ 3020 里，匹配的是"一对相邻城市共用一个天线"这个二元关系；在最小路径覆盖里，匹配的是"一个点在路径中紧接着另一个点"这个前后关系。两个模型长得像，本质完全不同。
5. 调试心得与常见错误速查
5.1 最容易翻车的五个细节
第一个经典的坑是左右部的划分。有人图省事，用城市编号的奇偶性来分左右部，也就是判断id % 2。这几乎必然出错，因为 id 是按扫描顺序分配的，两个相邻城市的编号可能一奇一偶，也可能同奇同偶，和坐标奇偶性没有半点关系。判断左右部只能用 (i + j) % 2，不能用 id % 2。
第二个坑是邻接表没清空。多组数据时，g 数组如果不 clear，上一组数据的边会残留到下一组，导致匹配数虚高或者直接越界。id 数组也要清零，否则上一组残留的编号会覆盖当前组。
第三个坑是 match 数组和 vis 数组的语义搞混。match[v] 里存的是右部顶点匹配的左部顶点编号；vis 标记的是右部顶点，每次从一个新的左部点出发找增广路之前必须 memset 清零。如果不清 vis，后面点的增广路径会被前面的访问标记挡住，匹配数偏小。
第四个坑是枚举方向建边时的数组越界。检查四个方向之前一定要先做边界判断，否则 dx dy 直接越界访问 mp，可能出现随机错误。第五个坑是匈牙利只从左部开始跑，如果你把左右部不分、对每个点都跑一遍 dfs，匹配计数可能不准。这是正确方向的问题，不是效率问题。
5.2 小数据手算验证方法
提交之前，我通常用手算小样例来验证建模和公式是否正确。比如一个 2 × 2 全*的网格：四个城市围成一个正方形，四个方向相邻，最大匹配显然是 2（横向两条或纵向两条），答案 = 4 − 2 = 2。手动检查：两个天线，一个覆盖上面两个，一个覆盖下面两个，确实最少 2 个。
再比如一列 3 个城市的竖条：城市链是 0-1-2，最大匹配是 1，答案 = 3 − 1 = 2。手动检查：一个天线覆盖前两个城市，剩下一个城市单独覆盖，总共 2 个，确实没法用 1 个天线，因为一个天线最多覆盖两个城市。这些边界样例能快速暴露建模错误，所以我建议拿到题目先自己在草稿纸上画几个小网格，把匹配数手算出来，再拿代码去对。
5.3 一个实用的自测技巧
我调试这类网格匹配题的习惯是：把最终匹配结果可视化。做法是在 dfs 跑完之后，遍历右部顶点，如果 match[v] 不是 -1，就把编号还原成坐标，打印一条(x1,y1) -- (x2,y2)的边。这样你能肉眼看到匹配的边是否合法：端点是否是相邻城市、有没有一个城市同时出现在两条匹配边里。如果发现同部边或者重复覆盖，马上就能定位到建边或者染色的逻辑错误。
还有一个经验是：输出答案之前，先输出 cnt 和 matching 两个中间值。cnt 算出来不对，说明编号映射有问题；matching 算出来不对，说明建边或者匈牙利实现有问题。把它们拆开看，比直接看最终答案容易定位得多。
6. 最后再分享一个实战心得
这道题我前前后后做过好几遍，每次重做都会发现新的理解。第一次 AC 的时候，我只是照着题解背了公式，代码抄过来改改就交了，根本没想明白为什么最小边覆盖等于点数减最大匹配。后来在一道路径覆盖题上栽了跟头，才回头把这两个模型彻底分清。
我现在面对这类题目，习惯先问自己三个问题：要覆盖的"东西"是什么？可以共用一个资源的"关系"长什么样？这个关系能不能天然构成二分图？POJ 3020 的答案分别是：城市、相邻城市对、以及棋盘染色的天然二部结构。想清楚这三个问题，代码怎么写其实都是次要的。如果你刚接触二分图匹配，我强烈建议把这道题和最小路径覆盖的题目放在一起做，对比着体会"同一个公式，两种完全不同的建模"，收获会大得多。
