AcWing 379. 捉迷藏

AcWing 379. 捉迷藏"/>

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

思路：
该题为求最小重复路径覆盖
首先理解什么是最小路径覆盖，就是用最少的路径覆盖所有的点，其中路径之间没有重复，问有多少条路径。
首先需要拆点，比如a->b，要拆成a->b’。之后跑一遍匈牙利，统计每条路径的终点。一条路径的终点一定是左侧的非匹配点，因为如果左侧匹配了，就意味着他可以到达其他点，就不是终点。所以只要统计终点，就可以知道有多少条路径！

但是这道题中，路径之间可以相交，就是最小重复路径覆盖问题。只需要在之前跑一遍传递闭包就可以了！
代码：

#include<iostream>
#include<cstring>
using namespace std;
int n,m;
const int N=1e3;
bool g[N][N],st[N];
int match[N];
bool find(int x)
{for(int i=1;i<=n;i++){if(g[x][i] && !st[i]){st[i]=true;if(match[i]==0 || find(match[i])){match[i]=x;return true;}}}return false;
}
int main()
{cin>>n>>m;for(int i=0;i<m;i++){int a,b;cin>>a>>b;g[a][b]=true;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]|=g[i][k]&&g[k][j];}}}int res=0;for(int i=1;i<=n;i++){memset(st,false,sizeof st);if(!find(i)){res++;}}cout<<res;
}