算法竞赛进阶指南 捉迷藏

最小点路径覆盖：对于一个有向无环图，用最少的互不相交的路径将所有的点覆盖。（这里的最少的互不相交的路径是指：边不重复，点也不重复）。

拆点：对于原图中(1, n)拆为新图中的(1', n')；

转化：将原图中的i -> j 转化为新图中的i -> j'。

如图将原图中的1 -> 2 -> 3转化为新图的路径即为：

1 -> 2', 2 -> 3'。

但是不能出现1 -> 2, 3 -> 2这样点就重复了 

因此得出两个结论：

1：路径 《==》 匹配

2：左部非匹配点 《==》路径终点，孤立的点也算一种特别的终点

 所以要求原图中最少的互不相交的路径，即原图中终点最少的路径，即求新图中左侧最少的非匹配点的数量(n - m)，即求新图中左侧最大的匹配数量(m)，即求最大匹配数(m), 最后用左侧所有点数(n) - 最大匹配数(m)即为最少的互不相交的路径。

        

扩展：最小路径点重复点覆盖：在最小路径点覆盖的基础上加上边和点可以重复即为最小路径重复点覆盖。

步骤：假设原图为G

1：求原图G传递闭包G'

2：则原图G中最小路径重复点覆盖 = 新图G'中最小路径覆盖；

证明：

首先先清楚什么是传递闭包：假如一条路径a -> b -> c则我们直接将点b忽略从a -> c连一条边求传递闭包用的是floyd算法若不懂floyd算法的可以看看这篇博客：

floyd 算法模板详解(适合新手)_wsh1931的博客-CSDN博客

传递闭包求法：题解：算法竞赛进阶指南 排序_wsh1931的博客-CSDN博客

即证明两个图G, G'等价。

在原图G中求传递闭包即将所有重复出现的点变为不重复出现的点：

即假设一条路径a -> b -> a -> e以点a为例根据传递闭包所形成的路径即为：

a -> b -> e.因此原图G中每一条路径在G'中都有路径与之配对即将重复的点跳过即为最小路径点覆盖.

同样将G'转化为G即将跳过的点还原，即将a -> b -> e还原为 a -> b -> a -> e。

因此G’中每一条路径都与G中每一条路径配对：即在G‘图中求最小路径点覆盖，即在G图中求最小路径重复点覆盖。

 
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 - res。

 
#include 
#include 
#include 
 
using namespace std;
 
const int N = 210;
 
int n, m;
int match[N];
bool d[N][N], 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] == -1 || find(match[i]))
            {
                match[i] = x;
                return true;
            }
        }
    }
    
    return false;
}
 
int main()
{
    cin >> 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];
    
    memset(match, -1, sizeof match);
    
    int res = 0;//求最大匹配数
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }
    
    cout << n - res << endl;//最小路径重复点覆盖 = 求传递闭包后的最小路径点覆盖 = n - res
    
    return 0;
}