匈牙利算法"/>
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
分析
- 先了解下最小路径覆盖:对于一个有向无环图(DAG),用最少的互不相交的路径,将所有点覆盖(互不相交是指点和边都不重复,其实就是点不重复,因为边重复那么点肯定也重复);
- 再了解下最小路径重复点覆盖:在最小路径覆盖问题的基础上,去掉互不相交的条件;然后有一个结论:如果原图是G,求完传递闭包的新图为G’,那么 G的最小路径重复点覆盖 == G’的最小路径覆盖;
- 题目思路:一个DAG图,n个点m条边,想找k个点,这k个点之间没有路(那就是每条最小路径的终点组成的集合),用最少的边,把所有点覆盖;正是因为这是最小路径,才保证了各个终点不会相互到达;为了避免最小路径重复,所以进行了求传递闭包;
- 程序思路:先求传递闭包,如果一个点间接连向另一个点,那我们直接连一条边,相当于加了很多边;类似于 a->b->c的边,直接加一条a->c的边;原图的最小路径重复点覆盖等价于新图的最小路径覆盖,所以在求完传递闭包的新图上求最小路径覆盖;然后利用下面的结论求得答案:n-res(n为点数,res为最小路径覆盖数、也为最大匹配数);
- 之前的最大独立集是和最大匹配数互补的(两者之和为总点数),最小路径点覆盖(最小路径覆盖)和最大匹配数也是互补的;那么结论就是:最小路径点覆盖(最小路径覆盖) = 总点数 - 最大匹配数;
- 二分图虽然是定义在无向图上的,但是我们只存了从左到右边(因为一直是枚举男生开始dfs的),当然也可以存从右到左的边,但是没必要,因为我们用不上,所以此题是有向图也不影响;
#include <bits/stdc++.h>using namespace std;const int N = 210;int n, m;
int d[N][N];//求完传递闭包的新图
int match[N];
int vis[N];bool dfs(int u) {for (int i = 1; i <= n; ++i) {//有边、未访问过if (d[u][i] && !vis[i]) {vis[i] = 1;if (!match[i] || dfs(match[i])) {match[i] = u;return true;}}}return false;
}int main() {cin >> n >> m;while (m--) {int a, b;cin >> a >> b;d[a][b] = 1;}//求传递闭包,把原来是间接的边,直接加一条直接连接的边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, 0, sizeof vis);if (dfs(i))res++;}cout << n - res;return 0;
}
更多推荐
379. 捉迷藏——最小路径覆盖+匈牙利算法
发布评论