• 这个概念是针对DAG（有向无环图）的。最小路径点覆盖又被称为最小路径覆盖，是指在一个DAG中，我们最少需要使用多少条互不相交（点和边都不重复）的路径将所有点都覆盖住。

• 这里使用到的技巧是拆点，假设原图中有n个点，将每个点都复制一份放在右边（此时新图中有2n个点），假设点$i$复制后的点为点$i’$，我们将边$(i, j)$变为新图中的$(i, j’)$。新图必然是一个二分图，在这个二分图中求最大匹配数m，则最终有：原图的最小路径点覆盖t == 原图总点数n - 新图的最大匹配数m。下面证明这个结论：

• 考虑原图中的任意一条路径转化到新图中是啥样的：

（1）每条路径转化到新图中一定对应新图的一个匹配，即每个点只会在一条边中。反之也成立。

（2）我们可以看一下原图中每条路径的终点，对应到新图中的出点是没有出边的，即左部的非匹配点，例如上图中的点3。同理左部的每个非匹配点一定也对应着原图中的路径。即使孤立点也可以看成一个终点，符合要求。

最小路径点覆盖$\iff$让左部的非匹配点最少$\iff$让左部的匹配点最多$\iff$找最大匹配。

• 综上所述，有：原图的最小路径点覆盖t == 原图总点数n - 新图的最大匹配数m。

• 最小路径重复点覆盖：也是针对DAG来说的；将最小路径点覆盖中路径不能相交的条件去掉即可，即我们最少用多少条路径（点和边都可以重复）可以将所有的点覆盖住。

• 求最小路径重复点覆盖的步骤如下：

（1）求原图的传递闭包得到新图；

（2）则原图的最小路径重复点覆盖$\iff$新图的最小路径点覆盖。

• 下面对上述等价性进行证明：

① 充分性：依次考虑原图的每条符合条件的路径，当我们考察到第i条路径时，如果路径上的点和前i-1条边上的点重复，则直接跳过即可，新图中加了很多边，可以跳过。另外第i条路径上的点不可能全部和前i-1条边上的点重复，否则的话第i条路径就没有存在的必要了。

② 必要性：将新图中间接转移过去的边展开成原来的边即可得到原图中的路径。

分析

• 分析题目可知，只要两个点存在一条路径，两者就是可以相互看到的（相当于人的视线可以拐弯的）。

• 该题相当于问：给定我们一个有向无环图，让我们选择尽可能多的点，使得这些点任意两点之间都不能相互到达。

• 首先说答案：答案 = 最小路径重复点覆盖的数量cnt。下面给出证明：

（1）首先一定有$K \le cnt$，否则一条路径上会选出两个点，会相互看见。接着证明K可以取到cnt。

（2）我们找出这cnt条路径的终点，这些终点肯定两两都不相同，否则的话某条路径上可以删除重复的终点，仍然符合要求。这些记为集合V，然后我们将这些终点所有能反向到达的点的集合记为$next(V)$。

​ （2.1）如果有$V \bigcap next(V) = \emptyset$，意味着我们从E出发是不可能到达V内部的点的，此时选择E中的cnt个点是符合要求的。

​ （2.2）如果有$V \bigcap next(V) \neq \emptyset$，则我们可以从V中选择出某一个终点$v_i$，我们让$v_i$沿着边反向向前走（向前走到的点仍然记为$v_i$），直到走到满足条件$v_i \not \in next(V -\{v_i\})$，一定是可以找到这样点$v_i$的，否则这条路径就是多余的。如果仍然不为空，继续选择另一个终点进行这样的操作，直到交集为空集为止。

• 根据上面的讲解可知：原图的最小路径重复点覆盖t == 原图总点数n - 原图对应闭包图构造的二分图的最大匹配数m。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 30010;

int n, m;
bool d[N][N];  // 邻接矩阵
int match[N];
bool st[N];

bool find(int x) {

    for (int i = 1; i <= n; i++)
        if (d[x][i] && !st[i]) {
            st[i] = true;

            if (match[i] == 0 || find(match[i])) {
                match[i] = x;
                return true;
            }
        }
    return false;
}

int main() {

    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        d[a][b] = true;
    }

    // 传递闭包
    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", n - res);

    return 0;
}