题解：P10938 Vani和Cl2捉迷藏

· · 题解

分析

可以观察到，本题给出了一个 DAG，并且可以看作要用“路径”覆盖整个图。由于“能互相望见”在本题中即为路径，所以这些路径是可相交的。而我们又可以发现，望，是可以一望到底的，也就是路径会本能地做到尽可能长。藏身点怎么选呢？由于所有路径都不是完全重合的，因此我们总可以在每条路径上选出一个藏身点。可见这是一个有向无环图可相交情况下的最小路径点覆盖问题。

upd 2025/1/22：本题更为严谨且直接的解法为：求原图的最长反链的长度。同样可以由 Dilworth 定理 得到上述结论。此处作为扩展，感性理解“选择藏身点”即可。

最小路径点覆盖问题

P2764 最小路径覆盖问题 是模板题。此问题定义如下：

给定有向无环图 G，用最少的不相交的路径覆盖所有的点。

路径不相交，是指一个点恰好出现在一条路径上。

解决方法：我们将所有的点分为入点和出点，即对于一条有向边 x\to y，x 是入点，y 是出点。通过这种分类方法构造二分图，则最少路径数量 = 原图点数 n 减去二分图的最大匹配数。在此不提路径打印的方法，与本题无关。

证明

由于所有路径不相交，所以路径数量应等于终点的数量。因为终点没有出边，所以当 x 的出边 out_x 没有参与最大匹配时，x 必须是终点。由此可知，当参与最大匹配的 out_x 最多时，作为路径终点的 x 就最少，从而选择最少的路径。

Plus - 最小路径可相交点覆盖问题

在原图中，从 x 到 y 的路径我们并不关心。由于路径可相交，只要 x 能到达 y，我们就一定能选出一条 x\to y 的路径来。于是只需要在 x,y 之间直接连一条边就可以了，避免了相交的问题，于是原问题又转化为新图下的最小路径点覆盖问题。显然，x 是否能到达 y 能用 Floyd 传递闭包维护。

下面给出参考代码：

#include <bits/stdc++.h>

#define debug(x) (cout << #x << " " << x << "\n")

using namespace std;

using ll = long long;

const int N = 205;

int T, n, m, ans, match[N];

bool vis[N], dis[N][N];

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] |= dis[i][k] && dis[k][j];
}

bool hungary(int cur) {
    for (int nxt = 1; nxt <= n; nxt++) if (cur != nxt && dis[cur][nxt] && !vis[nxt]) {
        vis[nxt] = 1;
        if (!match[nxt] || hungary(match[nxt])) {
            match[nxt] = cur;
            return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fill(dis[i] + 1, dis[i] + 1 + n, 0), dis[i][i] = 1;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        dis[u][v] = 1;
    }
    floyd();
    fill(match + 1, match + 1 + n, 0);
    ans = 0;
    for (int i = 1; i <= n; i++) { 
        fill(vis + 1, vis + 1 + n, 0);
        ans += hungary(i);
    }
    cout << n - ans << "\n";
    return 0;
}