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

分析

1. 先了解下最小路径覆盖：对于一个有向无环图(DAG)，用最少的互不相交的路径，将所有点覆盖（互不相交是指点和边都不重复，其实就是点不重复，因为边重复那么点肯定也重复）；
2. 再了解下最小路径重复点覆盖：在最小路径覆盖问题的基础上，去掉互不相交的条件；然后有一个结论：如果原图是G，求完传递闭包的新图为G’，那么 G的最小路径重复点覆盖 == G’的最小路径覆盖；
3. 题目思路：一个DAG图，n个点m条边，想找k个点，这k个点之间没有路（那就是每条最小路径的终点组成的集合），用最少的边，把所有点覆盖；正是因为这是最小路径，才保证了各个终点不会相互到达；为了避免最小路径重复，所以进行了求传递闭包；
4. 程序思路：先求传递闭包，如果一个点间接连向另一个点，那我们直接连一条边，相当于加了很多边；类似于 a->b->c的边，直接加一条a->c的边；原图的最小路径重复点覆盖等价于新图的最小路径覆盖，所以在求完传递闭包的新图上求最小路径覆盖；然后利用下面的结论求得答案：n-res（n为点数，res为最小路径覆盖数、也为最大匹配数）；
5. 之前的最大独立集是和最大匹配数互补的（两者之和为总点数），最小路径点覆盖（最小路径覆盖）和最大匹配数也是互补的；那么结论就是：最小路径点覆盖（最小路径覆盖） = 总点数 - 最大匹配数；
6. 二分图虽然是定义在无向图上的，但是我们只存了从左到右边（因为一直是枚举男生开始dfs的），当然也可以存从右到左的边，但是没必要，因为我们用不上，所以此题是有向图也不影响；

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int n, m;
int d[N][N];//求完传递闭包的新图
int match[N];
int vis[N];

bool dfs(int u) {
    for (int i = 1; i <= n; ++i) {
        //有边、未访问过
        if (d[u][i] && !vis[i]) {
            vis[i] = 1;
            if (!match[i] || dfs(match[i])) {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        d[a][b] = 1;
    }
    //求传递闭包，把原来是间接的边，直接加一条直接连接的边
    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(vis, 0, sizeof vis);
        if (dfs(i))
            res++;
    }
    cout << n - res;
    return 0;
}