POJ 3020 天线覆盖：二分图最大匹配与匈牙利算法建模

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]; // 坐标 - 城市编号 vectorint 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(); vectorint 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 的答案分别是城市、相邻城市对、以及棋盘染色的天然二部结构。想清楚这三个问题代码怎么写其实都是次要的。如果你刚接触二分图匹配我强烈建议把这道题和最小路径覆盖的题目放在一起做对比着体会同一个公式两种完全不同的建模收获会大得多。