小指针
2022/10/06阅读:92主题:凝夜紫
【图论专题】二分图中的最小路径点覆盖问题的求解思路
外部链接公众号无效,点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。
前置知识
最小路径点覆盖
在一个「有向无环图」中,用最少的互不相交的路径将所有点覆盖,我们叫做「最小路径点覆盖」,又称为「最小路径覆盖」。
「拆点」:把一个点拆分成两个点
1
,左边作为出点1
,右边作为入点
。
经过如上「拆点」的过程之后,我们发现一条边i->j
可以拆分成一条由i
指向
的一条边,这样我们就得到了一个二分图。
为什么这样分成的图是二分图呢?
注意,我们的拆点规则,我们是把「一个点分成两部分,边的出度总是在左边(左集合),边的入度总是在右边(右集合),也就是说不可能有边的两个端点全在左边或者全在右边的情况。」
用上述的方式,我们将「原图中的所有路径转化到新的二分图中」,因为原图有性质「路径都是互不相交的」,也就是说「原图中一个点只属于一条边」。
所以,转换到新图中就是「一个点只有一个入度和一个出度」,也就是说「左部的每一个点只会向右部连接一条边,右侧的每一个点也只属于一条边」。

总结一下:
-
原图中每条路径 和 新图(二分图)中的每个匹配是一一对应关系; -
还有一个隐藏的性质,「原图中每个路径的终点 和 新图(二分图)中 左边的某个 非匹配点 是对应的」。
综上,根据上述两条性质,我们先把原问题「求原图中最少的互不相交的路径数量」等价变形成「求互不相交的路径终点数量最少」,等价于「求左边非匹配点的数量最少」,等价于「求左边匹配点的数量最多」(总点数减去匹配点就是非匹配点),而左侧每个匹配点都对应一个匹配,所以问题最终转换为「求新图(二分图)的最大匹配数量」。
最小路径重复点覆盖
扩展概念,在上面的内容里,我们求的是「用最少的互不相交的路径将所有点覆盖」,所以称为「最小路径点覆盖问题」;那么取消掉「互不相交」这个条件,我们称为「最小路径重复点覆盖问题」。
解决该扩展问题只需要两步:
-
在原图
G
上面求传递闭包,得到新图 。求传递闭包,相当于在原图上增加了很多边,比如:原来边1->2->3
,则根据传递性增加一条边1->3
。 -
在新图 上求「最小路径覆盖」即可。
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)取交集,则会出现两种情况:
-
「两者交集为空集」,说明我们从
集合E
的任何一个点出发,都不可能到达集合E
内部的任何点,也就是说集合E
里面的点是不能相互到达的,那么因为集合E
里面总共有「cnt」个点,所以我们就构造出了一种方案K==cnt
。 -
「两者的交集为非空集」,从
集合E
中选择出某一个点ei
,让ei
一直沿着它的边往前走,直到走到ei
不属于next(E)
为止。对集合E
中的每个ei
都执行这种操作。全部执行完成之后就可以得到「两者交集为空集」的情况。 -
还存在一个问题,对于每个
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」
作者介绍