题解：AT_abc274_g [ABC274G] Security Camera 3

Inter12 · 2024-12-16 17:20:53 · 题解

题意

我们先审题意，发现：

如果我们只看一行或者一列的时候，出现的一个不带有障碍的连续范围内的格子（也就是一个在一行或者一列中的连通块）会被一个监控发现。
当我们只看一个不是障碍的格子的时候，我们会发现，只看他所对应的第 i 行中，有一个连通块，而只看他所对应的第 j 列时，也有一个连通块，那么就出现了选择：要么在行向的连通块上放置一个监控，要么在列向放置一个监控，或者两个都放，使其被监控范围罩住，这样就出现了至少二选一的情形。

二分图最小点覆盖

而，至少二选一的特性，就正好对应上了二分图最小点覆盖的特性。

而二分图最小点覆盖的答案和二分图最大匹配的答案一样（待会会讲证明），因此，我们可以如下建模：

将行看作型号为 A 的点，将列看作型号为 B 的点；
给每一个连通块（也就是只看每一行每一列的连通块）编上号，连通块中的每一个点都会拥有两个编号，一个是 A 型号上的连通块编号，一个是 B 型号上的。统计 A 型号上或者 B 型号上的连通块数量；
遍历全图，如果出现空地，就将 A 型号上的连通块编号连向 B 型号上的联通快编号（如果你前文统计的是 B 型号上的连通块数量，就正好相反），一般建的都是单项边。

讲完建模，这里回应前文，讲一下为什么二分图最小点覆盖的答案和二分图最大匹配的答案一样。

证明（忙的请跳过）

证明方法一：

借鉴巨佬@金珂拉帖子里的求解方式。

用网络流最大权闭合子图证明二分图最大点覆盖等于其最大匹配：

我们发现网络流最大权闭合子图的构造是 i 到 j 有边，则意味着有 i \to j 的约束条件，同时正权点与 S 连边，负权点与 T 连边。

然后二分图最大点覆盖有一个性质：对于两边的点 a_i,b_j 若他们之间有一条边，则意味着他们中至少有一个需要被选取到点覆盖内。

根据集合论的知识：

p∣q=!p \to q

则我们对于每个左侧节点 i，新建节点否 i，现在我们要求一个最大的集合，假设我们先让所有的左侧节点进入集合。因为我们要集合的元素个数最小，所以我们每次拿出一个节点（也就是在最大权闭合子图中选取了左侧节点的否节点）计为 1，放入一个节点（选取右侧节点）则计为 -1，最后求最大权闭合子图即可。

观察最大权闭合子图，容易发现，若不考虑边权，其构造恰好与二分图最大匹配的构造相同。因为每个点最多只有一个入流，所以本来为正无穷的边其实与 1 的边是相同的。所以实际上最大权闭合子图的最小割与二分图最大匹配的最大流一模一样！

于最大权闭合子图需要先累加正权点，也就是 num_{lt}，而这里最大权的意义又恰好是在只有左侧节点的点集中删去最大权个数的点。

也就是说最后的答案是 num_{lt} - (num_{lt} - mxflow) = mxflow，也就是二分图最大匹配。

证明方法二：

更简单，更易懂。

设二分图最小覆盖为 s 个，最大匹配 ans 条；
由于最大匹配的 ans 条边不共点，那么覆盖 ans 条边至少需要 ans 个点，也就是 ans \leq s，第一步成立；
从点集内每个点都可以找到一个匹配，否则就可以删除选择这个点，也不影响整个选点，反而更优。因此可以选至少 s 条边，得到大小至少为 s 的匹配，s \leq ans，第二步成立；
所以 s = ans 恒成立。

代码（主函数核心代码）：

cin >> n >> m;
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        cin >> field[i][j];
siz = 1;
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m + 1; j++)
        if(field[i][j] == '.')
            id[i][j][0] = siz; // id[i][j][0] 表示 (i, j) 点上位于行向的连通块的编号 
        else
            siz++; // 遇到障碍连通块就断掉了，需要加一 
int n1 = siz - 1; // 减一是因为最后还加了一次，需要在统计 A 型号上的连通块数量时减一
for(int i = 1; i <= m; i++)
    for(int j = 1; j <= n + 1; j++)
        if(field[j][i] == '.')
            id[j][i][1] = siz; // id[i][j][1] 表示 (i, j) 点上位于列向的连通块的编号 
        else
            siz++;
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(field[i][j] == '.')
            nbr[id[i][j][0]].push_back(id[i][j][1]); // 连有向边 
for(int i = 1; i <= n1; i++)
{
    if(hungary(i, ++tim)) // 打时间戳减少时间消耗 
        ans++;
}
cout << ans << '\n';