题解：P10938 Vani和Cl2捉迷藏

· · 题解

传送门：P10938 Vani和Cl2捉迷藏

简要题意：

给定一张有向无环图，现在需要选出最多的点，使得它们之间无法互相到达。

分析：

  1. 若答案的点集中有某个点，这个点就会占掉图中一条路径，我们能不能看作是选路径而不是选点呢？

  2. 从路径的起点可以一眼看到底，所以路径是天然最长的。不可能出现一条路径没有选到底的情况。是不是一定有方案使得选择每条路径上的一个点，他们两两无法到达？考虑两条路径相交的情况，如果无法选出这样的两个点，说明对于两条路径上的任意两点，都可以由其中一个到达另一个。那么我们固定其中一条路径的方向，两条路径的起点相通，起点方向一致；两条路径的终点也相通，终点方向也一致。那么这两条路径就可以合并成一条更长的路径，不符合路径最长的规则。我们就用反证法证明了两条路径相交的情况一定有方案。合并这两条路径，此时再加入其他的路径就又回到了我们刚刚讨论的两条路径的模型，是相同的。所以刚刚的讨论可以扩展到整张图。所以只要路径最长，就一定有方案使得选出的点集两两无法到达。所以可以将题意转换为选路径覆盖所有的点，且每条路径必须极长。

  3. 路径最长意味着路径数最少，问题转换为路径可以相交的最小路径点覆盖问题。

  4. 首先你需要掌握P2764 最小路径覆盖问题模板，接下来我们考虑如何处理“路径可以相交”这一区别。让我们手玩一张最简单的图：

如果路径不能相交，那么这张图的最小路径点覆盖为 3。但是如果可以相交，那么答案显然为 2。

由于我们不关心具体选的边，只关心最少的边的数量，所以 4 \to 2 \to 5 这条边等价于一条 4 \to 5 的边。如果我们加入这条边，那么就可以在路径不能相交的情况下选出 1 \to 2 \to 3 和 4 \to 5（实际上是 4 \to 2 \to 5）这两条边。按照这样的想法，我们对原图跑一遍传递闭包，只要从点 x 可以到达点 y，我们就让 x 向 y 建边，这样就可以找出路径可以相交的最小路径点覆盖了。

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 205;

int n, m, match[N], vis[N], tim, ans;

bool f[N][N];

vector<int> nbr[N];

bool haha(int cur) {
    for (auto nxt : nbr[cur]) {
        if (vis[nxt] == tim) continue;
        vis[nxt] = tim;
        if (!match[nxt] || haha(match[nxt])) {
            match[nxt] = cur;
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        f[x][y] = true;
    }
    for (int i = 1; i <= n; i++)
        f[i][i] = true;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] |= (f[i][k] && f[k][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i != j && f[i][j]) {
            nbr[i].push_back(j);
        }
    for (int i = 1; i <= n; i++) {
        tim ++;
        if (haha(i)) ans ++;
    }
    cout << n - ans << "\n";
    return 0;
}