# 前置知识

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

# 最小路径点覆盖

在一个有向无环图中，用最少的互不相交的路径将所有点覆盖，我们叫做最小路径点覆盖，又称为最小路径覆盖。
拆点：把一个点拆分成两个点 1 ，左边作为 出点1 ，右边作为 入点 $1^\prime$ 。

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

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

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

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

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

总结一下：

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

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

# 最小路径重复点覆盖

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

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

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

# 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

经典必会 AcWing算法提高课匈牙利算法二分图的最小路径点覆盖