AcWing 379. 捉迷藏/(二分图-最小路径覆盖)/(匈牙利算法)
原题链接
中等
作者:
殇ベ_11
,
2021-05-23 11:13:52
,
所有人可见
,
阅读 390
题目描述
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
C++ 代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 210, M = 210000;
int n,m;
bool d[N][N];
bool vis[M];
int match[M];
int find(int x) //匈牙利算法
{
for(int i = 1;i <= n;i ++){
if(d[x][i] && !vis[i]){
vis[i] = true;
if(!match[i] || find(match[i])){
match[i] = x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
memset(d, false, sizeof(d));
for(int i = 1;i <= m;i ++){ //标记
int x,y;
scanf("%d%d",&x,&y);
d[x][y] = 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(vis,false, sizeof(vis));
if(find(i)) res ++;
}
printf("%d",n - res); //最小路径覆盖数 = 点数 - 最大匹配!!
return 0;
}