外部链接公众号无效，点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。

前置知识

图论基础之二分图中最小覆盖问题的求解思路

最小路径点覆盖

在一个「有向无环图」中，用最少的互不相交的路径将所有点覆盖，我们叫做「最小路径点覆盖」，又称为「最小路径覆盖」。

「拆点」：把一个点拆分成两个点1，左边作为出点1，右边作为入点 。

经过如上「拆点」的过程之后，我们发现一条边i->j可以拆分成一条由i指向的一条边，这样我们就得到了一个二分图。

为什么这样分成的图是二分图呢？

注意，我们的拆点规则，我们是把「一个点分成两部分，边的出度总是在左边（左集合），边的入度总是在右边（右集合），也就是说不可能有边的两个端点全在左边或者全在右边的情况。」

用上述的方式，我们将「原图中的所有路径转化到新的二分图中」，因为原图有性质「路径都是互不相交的」，也就是说「原图中一个点只属于一条边」。

所以，转换到新图中就是「一个点只有一个入度和一个出度」，也就是说「左部的每一个点只会向右部连接一条边，右侧的每一个点也只属于一条边」。

总结一下：

原图中每条路径和新图（二分图）中的每个匹配是一一对应关系；
还有一个隐藏的性质，「原图中每个路径的终点和新图（二分图）中左边的某个非匹配点是对应的」。

综上，根据上述两条性质，我们先把原问题「求原图中最少的互不相交的路径数量」等价变形成「求互不相交的路径终点数量最少」，等价于「求左边非匹配点的数量最少」，等价于「求左边匹配点的数量最多」（总点数减去匹配点就是非匹配点），而左侧每个匹配点都对应一个匹配，所以问题最终转换为「求新图（二分图）的最大匹配数量」。

最小路径重复点覆盖

扩展概念，在上面的内容里，我们求的是「用最少的互不相交的路径将所有点覆盖」，所以称为「最小路径点覆盖问题」；那么取消掉「互不相交」这个条件，我们称为「最小路径重复点覆盖问题」。

解决该扩展问题只需要两步：

在原图G上面求传递闭包，得到新图。求传递闭包，相当于在原图上增加了很多边，比如：原来边1->2->3，则根据传递性增加一条边1->3。
在新图上求「最小路径覆盖」即可。

AcWing 379. 捉迷藏

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

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

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

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

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

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

「输入格式」
输入数据的第一行是两个整数 N 和 M。

接下来 M 行，每行两个整数 x,y，表示一条从 x 到 y 的有向道路。

「输出格式」
输出一个整数，表示最多能选取的藏身点个数。

「数据范围」
N≤200,M≤30000
「输入样例」
7 5
1 2
3 2
2 4
4 5
4 6
「输出样例」
3

题目描述

给出一个有向无环图，有N个点M条边，选出K个点，这K个点中任意两点之间都没有路径相连。问K最大为多少。

题目分析

假设「最小路径重复点覆盖」的数量是cnt个，则我们要选出来的K个点一定是从cnt个点中选出来，并且每条路径上最多只能选择一个点，因为如果一条路径选两个点，则可以通过这两个点观察到对方，与题面不符合，所以一定有K<=cnt。

那如果我们能构造出一种方案使得K==cnt，则就可以证明cnt就是题目的答案，因为K<=cnt，我们想让K最大。

「构造出K==cnt的方案」：

集合E：我们找出cnt条路线的所有终点，总共有cnt个，把这些终点全部放到「集合E」中；
next(E)：这是一个函数，它的返回值是「从E中的每个点出发，可以到达的所有点的集合」。
让E和next(E)取交集，则会出现两种情况：
1. 「两者交集为空集」，说明我们从集合E的任何一个点出发，都不可能到达集合E内部的任何点，也就是说集合E里面的点是不能相互到达的，那么因为集合E里面总共有「cnt」个点，所以我们就构造出了一种方案K==cnt。
2. 「两者的交集为非空集」，从集合E中选择出某一个点ei，让ei一直沿着它的边往前走，直到走到ei不属于next(E)为止。对集合E中的每个ei都执行这种操作。全部执行完成之后就可以得到「两者交集为空集」的情况。
3. 还存在一个问题，对于每个ei来说，是否一定能停止呢？答案是肯定的，最多走到起始点就停止了。我们考虑ei一直往后退，退到起点还是不能满足ei不属于next(E)，说明ei这个点的所在路径的起点都可以被其他路径到达，它就没有存在的价值了，因为它可以和到达它的路径接在一起，成为同一条路径，但是注意我们的cnt已经是最小的了，不存在更小的了，所以产生了矛盾，进而说明每个ei一定是能走到next(E)的。

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 30010;
int n, m;
int match[N];
bool d[N][N], st[N];

bool find(int u) {
    for (int i = 1; i <= n; i ++ ) {
        if (d[u][i] and !st[i]) {
            st[i] = true;
            int t = match[i];
            if (t == 0 or find(t)) {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        int a, b;
        scanf("%d%d", &a, &b);
        d[a][b] = true;
    }
    // floyd算法求传递闭包
    for (int k = 1; k <= n; k ++ ) 
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= n; j ++ )
                d[i][j] |= d[i][k] & d[k][j];
    // 匈牙利算法求二分图的最大匹配
    int res = 0;
    for (int i = 1; i <= n; i ++ ) {
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }
    printf("%d", n - res); // 总点数 - 最大匹配点
    return 0;
}

「END」