企业官网建设流程全解析

第一眼看 Antenna Placement 这题，我差点把它当成通信工程的选址问题。点开样例才发现，地图就是一张由星号和字母 o 组成的网格，星号是城市，o 是空地。题目用一大段话描述天线覆盖规则，翻译成人话其实只有一句：每个天线要么只罩住一个城市，要么罩住上下左右相邻的两个城市。问的是最少需要几个天线。

就这么简单的一句话，当年绕进去的人不在少数。等你看穿它之后，会发现这是一个非常纯粹的二分图匹配问题，用来理解“最小边覆盖 = 顶点数 - 最大匹配”这个结论，再合适不过。如果你是刚学匈牙利算法、看到匹配题不知道该往哪个方向想，这题值得完整推一遍。下面我按自己的理解顺序，把从题意到代码再到提交坑的完整链路拆开讲。

1. 题意转译：天线覆盖规则只有一句话，但包装得很厚

1.1 原题规则到底说了什么

原题给了一张 h 行 w 列的网格图，* 表示城市，o 表示空地。一个天线可以覆盖一个城市，也可以覆盖一个城市以及它上下左右四个方向上相邻的另一个城市。求覆盖所有城市需要的最少天线数。

这里有两个容易被忽略的关键限制：

• 天线能覆盖的“两个城市”必须是上下左右相邻的，不能斜着配，更不能隔一个格子配。
• 每个城市虽然可以被多个天线覆盖（题目允许重复覆盖），但正常思考时我们不会让天线去覆盖已经被覆盖过的城市，那是纯浪费。

所以问题本质就一句话：把城市两两配对，让配对的相邻城市共用一个天线，问最多能配出多少对。每配出一对，天线总数就比“每个城市单独放一个天线”少一个。

1.2 拿最小样例推演一遍

我习惯用一个小数据验证模型，比如：

2 3 *o* *oo

三个城市分别在 (0,0)、(0,2)、(1,0)。其中 (0,0) 和 (1,0) 上下相邻，可以共用一个天线；剩下 (0,2) 跟谁都不相邻，只能独占一个天线。所以答案是 2。

看这个关系：

• 城市总数 cnt = 3
• 最大能配成的相邻对 = 1
• 答案 = cnt - 1 = 2

再试一个 2x2 全城市：

2 2 ** **

四个城市围成一个正方形，可以配成上下两对，或者左右两对。最多配出 2 对，答案就是 4 - 2 = 2。

这两个样例基本可以说明：答案永远是“城市总数减去最大配对数量”。至于怎么求最大配对数量，就是二分图最大匹配的事了。

1.3 一句话模型

把每个城市看成图上的一个顶点，两个相邻的城市之间连一条边。问题变成：

在这个图上，最多能选出多少条互不共享端点的边？

选出的一组互不共享端点的边，在图论里就叫匹配，最多的那组是最大匹配。用 ν 表示最大匹配的边数，答案就是 cnt - ν。

2. 建模细节：为什么网格图是天然的二分图

2.1 国际象棋棋盘染色的威力

看到网格里的“相邻关系”，我第一反应是给格子按棋盘点染色：坐标为 (i+j) 偶数的格子染成黑色，奇数的染成白色。

任意一次上下左右移动，坐标和 i+j 的奇偶性都会翻转。也就是说，只要两个格子相邻，它们必然一个是黑色、一个是白色。同色格子之间永远不可能有边。

城市邻接图有了这个性质，天然就是一个二分图：所有黑色城市属于左部，所有白色城市属于右部，边只可能在左右两部之间出现。这个性质决定了我们可以直接用匈牙利算法，而不需要处理一般图的“带花树”那种复杂匹配。

这里有一个通用判断技巧：以后遇到棋盘类问题，先问一句“相邻关系会不会跨越颜色分组”。只要满足这一步，二分图匹配的整套工具就能直接搬过来。

2.2 三步建图

整个过程我总结成三步，顺序不能乱。

第一步，给城市编号。遍历网格，遇到 * 就分配一个从 1 开始递增的编号，存到二维数组 id 里。这一步把网格坐标映射成图论顶点编号，方便后面建邻接矩阵。

第二步，确定左部顶点。约定坐标为 (i+j)%2==0 的城市是左部点，反正是右部点。左右部是相对的，只要保证边只从一边连到另一边就行。

第三步，连边。只遍历左部点，检查它上下左右四个方向，如果邻居也是城市，就建立一条从左部点指向右部点的有向边，在邻接矩阵里置 1。

代码如下：

for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (id[i][j] && (i + j) % 2 == 0) { leftList[++leftCnt] = id[i][j]; for (int k = 0; k < 4; ++k) { int ni = i + dx[k], nj = j + dy[k]; if (ni >= 0 && ni < h && nj >= 0 && nj < w && id[ni][nj]) g[id[i][j]][id[ni][nj]] = 1; } } } }

城市数最多 400 左右，邻接矩阵开 405x405 完全够用，不用折腾邻接表。

2.3 一个隐藏雷区：无向建图会让匹配数翻倍

我在第一次做这题时踩过一个很实际的坑：想着“相邻就建边”很自然，于是把所有相邻城市都双向建边，g[u][v] 和 g[v][u] 都置 1，然后直接跑匈牙利。

结果最大匹配记录下来总是真实值的两倍，答案算出来全乱了。

原因是：一条实际相邻边 (u,v)，当从左部视角做增广时会成功一次；但如果在主循环里把每个顶点都当作左部点跑一遍，从 v 出发又会对同一条边再成功一次。于是每一条真实匹配边被统计了两次。

解决方式有两种：

• 推荐做法：按奇偶染色只建单向边，主循环只遍历真正的左部点，匹配数不用除以任何东西。
• 如果想偷懒双向建边，那输出答案时必须写成 cnt - maxMatch / 2，心里时刻记着那个除以 2 的修正。

这两种写法在题解区都有人用，只看你更信任哪一种。

3. 最小边覆盖 = 点数 - 最大匹配，先把这句话真正想通

3.1 这题为什么是“最小边覆盖”

天线的放置方案放到图上，其实就是在选一组“覆盖结构”：一个天线覆盖单个城市，等价于一条只关联一个顶点的退化边；一个天线覆盖两个相邻城市，等价于选一条普通边盖住两个顶点。

目标是让每个城市至少被一个天线盖到，同时天线总数最少。这就是图论里的最小边覆盖问题，只不过这道题里允许了“退化边”的存在，让覆盖语义更贴近原题。

最小边覆盖有一条著名公式：对于不含孤立点的无向图，最小边覆盖数 = 顶点数 - 最大匹配数。原题的城市图甚至不需要排除孤立点，因为孤立城市就直接单独放一个天线，公式依然成立。

3.2 用“省天线”的思路推导公式

我不喜欢死记公式，更愿意用省天线的逻辑推一遍。

假设一开始每个城市都单独放一个天线，总共需要 cnt 个天线。现在考虑让两个相邻城市共用一个天线，每成功配对一对，天线总数就减 1。

但要注意，一个城市只能参与一次“共用”。如果城市 A 已经和 B 共用了一个天线，它就不能再和 C 共用另一个天线了，否则城市 A 同时被两个天线覆盖，纯属浪费。这意味着所有“共用天线”的城市对必须两两不重叠，正好就是匹配的定义。

所以最多能省下的天线数，就是图上最大匹配的边数 ν。最小天线数 = cnt - ν。

反过来看任意一个覆盖方案：里面所有“两城天线”的配对关系可能互相交叠，一旦交叠就说明有城市的配对机会被浪费了。想让省下的天线数最大，所有配对必须互不重叠，也就是必须构成一个匹配。最大匹配只有 ν 条边，所以任何方案最多只能省下 ν 个天线。下界和上界碰到一起，公式就成立了。

3.3 一个简单的例子：为什么贪心配对不够，需要“拆开重配”

有同学可能会想，直接扫描城市，见到相邻就配对，不也是一种“最大配对”吗？还真不一定。

看这个四城市的 L 形布局：

*** *oo

四个城市分别在 (0,0)、(0,1)、(0,2)、(1,0)。(0,0) 和 (0,1) 相邻，(0,1) 和 (0,2) 相邻，(0,0) 和 (1,0) 相邻。最大匹配是 2，比如 (0,0) 配 (1,0)，(0,1) 配 (0,2)，答案 = 4 - 2 = 2。

如果一开始贪心先让 (0,0) 配 (0,1)，那么剩下 (0,2) 和 (1,0) 各自只能单独放天线，总天线数变成了 3。这就不是最优。

匈牙利算法处理这个局面的方式，本质上就是“拆开重配”。想象从左部点出发找增广路径：如果目标右部点已经被占，就去看占用它的那个左部点能不能改配别的右部点；能改的话，就一路倒推回去重新调整匹配关系，最终让总匹配数增加 1。看到这里你应该明白了，匹配问题里的贪心之所以不靠谱，是因为缺少了一条“反悔”路径。

4. 匈牙利算法落地：关键状态设计与完整代码

4.1 三个状态数组的含义

在我给出的模板里，有三个数组需要先搞清楚，否则代码看多少遍都像天书。

• match[v]：右部点 v 当前匹配到的左部点是哪个。初始为 0 表示还没被匹配。
• vis[v]：在当前这一轮增广中，右部点 v 是否已经被访问过。每一轮主循环开始前都要清空。
• g[u][v]：二分图邻接矩阵，表示左部点 u 到右部点 v 有没有边。

dfs(u) 做的事情很单纯：尝试给左部点 u 找一个右部点 v 完成匹配。v 有两个选择：要么 v 本来就没人占，直接匹配；要么 v 已经被某个左部点 match[v] 占了，那就递归尝试让 match[v] 去找别的右部点。只要递归成功，u 就能顺理成章占住 v。

这个递归过程就是前文说的“拆开重配”，也是匈牙利算法的精髓。

4.2 可直接提交的完整代码

#include <cstdio> #include <cstring> const int MAXN = 405; char mp[55][55]; int id[55][55]; int g[MAXN][MAXN]; int match[MAXN]; int vis[MAXN]; int h, w, cnt; int leftList[MAXN], leftCnt; bool dfs(int u) { for (int v = 1; v <= cnt; ++v) { if (g[u][v] && !vis[v]) { vis[v] = 1; if (match[v] == 0 || dfs(match[v])) { match[v] = u; return true; } } } return false; } int main() { int T; scanf("%d", &T); int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; while (T--) { scanf("%d%d", &h, &w); for (int i = 0; i < h; ++i) { scanf("%s", mp[i]); } 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; } } } memset(g, 0, sizeof(g)); memset(match, 0, sizeof(match)); leftCnt = 0; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (id[i][j] && (i + j) % 2 == 0) { leftList[++leftCnt] = id[i][j]; 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 && id[ni][nj]) { g[id[i][j]][id[ni][nj]] = 1; } } } } } int maxMatch = 0; for (int k = 1; k <= leftCnt; ++k) { memset(vis, 0, sizeof(vis)); if (dfs(leftList[k])) { ++maxMatch; } } printf("%d\n", cnt - maxMatch); } return 0; }

代码里最值得注意的一行是leftCnt的收集：我并没有遍历 1 到 cnt 的所有顶点去跑 dfs，而是只收集了 (i+j)%2==0 的左部点。这样既避免了对右部点做无意义增广，也从根本上杜绝了“匹配数翻倍”的问题。

4.3 复杂度估算

匈牙利算法的 DFS 版本复杂度是 O(VE)。在这个题里，顶点数最多 400，每个城市最多向四个方向建边，边数不超过 4cnt，整个复杂度非常宽松，随便跑。

这个复杂度结论以后可以复用：只要城市数能控制在 10^3 级别，DFS 版匈牙利就是首选，写起来最短，调起来也最直观。如果城市数大到上万，再考虑 BFS 版或 Hopcroft-Karp 算法，那是后话。

5. 提交过程中最常踩的五个坑

5.1 多组数据之间忘了清空

题目是多组测试，每组开头一个整数 T。最容易犯的错是 id 数组没有清空，导致上一组城市的编号残留到这一组，建图时 id[ni][nj] 判断到旧编号，很可能把根本不存在的边建出来，轻则答案错，重则数组越界直接 RE。

清理方法很简单：每组开始前对 id、g、match 全部 memset。代码里我写的是memset(id, 0, sizeof(id))，这是保命操作。

5.2 scanf("%s") 与相邻字符

网格每行是一串连续字符，没有空格，用scanf("%s", mp[i])最稳。它会自动跳过换行符和行首空白，不用纠结getchar()吃不吃回车的问题。

这里有个容易忽略的细节：如果题目描述里网格行与行之间没有任何空白，%s也能正确读取；如果哪天题目改成有空格分隔的字符，就得换成scanf(" %c", &mp[i][j])，注意%c前面的空格不能丢。3020 这套题用%s就好。

5.3 匹配数要不要除以 2

这是本题目测时最常见的“为什么答案和样例差很多”的根源。

• 单向建边 + 只遍历左部点：maxMatch 直接就是真实最大匹配数，答案 = cnt - maxMatch。
• 双向建边 + 遍历所有城市：maxMatch 统计了两遍，答案 = cnt - maxMatch / 2。

如果你写完代码发现输出样例结果偏小，先检查是不是建了双向边却没除以 2。这个检查只需要三秒钟，但肉眼找 bug 可能要十分钟。

5.4 奇偶染色的方向写反

如果判断条件写成了(i + j) % 2 == 1才连边，相当于左右部对调，本身不影响结果——但如果你连边条件和 leftList 收集条件不一致，就会出现“收集的左部点全是右边，但连边时只给右边的邻居连了边”这类错位。

更常见的问题是：只在左边点判断，但左边点集合收集错了，导致根本没有从左部到右部的边。症状非常典型：maxMatch 永远是 0，输出永远是 cnt。看到这种输出，第一个就该怀疑染色方向。

5.5 自己构造几个小数据做回归

提交前我会习惯性地造三组数据：

1 2 2 ** **

期望输出 2。这组验证基本配对逻辑。

1 2 3 *** *oo

期望输出 2。这组验证“拆开重配”是否真的被匈牙利算法正确处理，也就是第 3.3 节那个 L 形布局。

1 1 3 *?*

等一下，这里写出来是三个字符，如果中间那个不是城市，第三组专门测孤点。比如：

1 1 3 * o *

但网格输入不带空格，所以用：

1 1 3 *o*

两个城市被空地隔开，互不相邻，期望输出 2。这组验证孤立城市也能被正确计入答案。

这三组小数据如果都能过，代码的框架基本没问题。剩下的就是交上去看评测结果。

一些零零碎碎的调试体会

最后说点个人调试经验。遇到这道题答案不对时，我一般不会直接去翻题解，而是先打印 maxMatch 看是多少。如果 maxMatch 是 cnt 的级别，比如城市 40 个匹配出来 25，多半是双向建图没除以 2；如果 maxMatch 是 0，多半是奇偶染色条件写反或者 leftList 没收集对。

把这题吃透之后，棋盘类的匹配题基本都能一眼看出建图方式。只要看到网格、地图、相邻关系，先做二染色，再判断要的是最大匹配、最小点覆盖还是最小边覆盖。3020 最值得借鉴的点就是：它用一个看起来很“工程”的外壳，把最小边覆盖和最大匹配之间的等价关系藏得恰到好处，推通一次，后面的题就顺了。