P10938 - Vani 和 Cl2 捉迷藏

题目地址：P10938

题目难度：省选/NOI-

Vani 和 cl2 在一片树林里捉迷藏。

这片树林里有 座房子， 条有向道路，组成了一张有向无环图。

树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。

如果从房子 沿着路走下去能够到达 ，那么在 和 里的人是能够相互望见的。

现在 cl2 要在这 座房子里选择 座作为藏身点，同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找，为了避免被 Vani 看见，cl2 要求这 个藏身点的任意两个之间都没有路径相连。

为了让 Vani 更难找到自己，cl2 想知道最多能选出多少个藏身点。

对于 的数据，，，。

乍一看好像求最大点独立集的问题，但是它只存在于无向图中，题目所给是有向图。这道题的答案是该图的最小重复路径点覆盖的路径条数。那么什么是路径点覆盖呢？

在图上选取若干条互不相交的路径，并让这些路径不重不漏覆盖到每一个点。符合上述要求且总数最小的方案就叫做原图的最小路径点覆盖，图中每个节点均只被覆盖一次。而最小重复路径点覆盖则是允许选取的路径相交，即某个点至少被覆盖一次。

在二分图中，最小路径点覆盖的路径条数等于总点数减去最大匹配数；最小路径重复点覆盖的数量则需要先求传递闭包，再计算最小路径点覆盖得出。

这启发我们可以把图转化为二分图来做，具体流程如下：

1. 原图中的点 ，在二分图中变为 和
2. 对于原图所有形如 的边，在二分图上连 ；对于所有形如 的边，在二分图上连边

就可以把原图当二分图求解了。

接下来证明为什么答案就是原图的最小重复路径点覆盖。设答案为 、原图最小重复路径点覆盖数为 ，即证明 ：

1. 证明 ，考虑最小路径点覆盖的定义：因为 条路径已经把所有点覆盖了，选点只能选其中某条路径的某个端点，已知有道路相连的房屋是可以互相看到的，所以不可能同时选某条路径的两个端点（最多选一个）。因此选出的 是一定小于等于 的。
2. 证明 ，考虑构造：将所有路径的终点 放入一个集合 中， 为“从 出发能够到达的所有点的集合”。如果 ，均有 ，意味着 内任意两点不互通，此时 为一组合法方案，大小为 ；反之，让当前的 沿有向边反着走直到满足上面的情况。若当前点已经退回到它的起点，都还不满足上述情况，意味着这个起点与 中的所有点都互通，我们完全可以让 作为起点，所有点也都能被覆盖到，此时的最小路径点覆盖数为 ，与原图最小路径点覆盖数为 矛盾。故一定存在 。
3. 综上， 必定成立。证毕。

此时使用匈牙利算法跑二分图最大匹配，然后就可以得出答案了。时间复杂度 ，实际上会远小于此。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
#define N 210
#define M 30010
using namespace std;

bool g[N][N];
int match[N];
bool st[N];
int n, m;

bool hungary(int u) {
    for (int i = 1; i <= n; i++) {
        if (g[u][i] && !st[i]) {
            st[i] = true;
            if (!match[i] || hungary(match[i])) {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

void floyd() {
    // Floyd 传递闭包
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g[i][j] |= g[i][k] & g[k][j];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }
    floyd();
    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(st, false, sizeof st);
        if (hungary(i)) res++;
    }
    cout << (n - res) << endl;
    return 0;
}

瓦尼瓦尼和氯气？