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;
}
更多推荐
AcWing 379. 捉迷藏
发布评论