受益
- 这个题很好的让人知道了之前的二分图性质均是针对无向图的
DAG的最小路径覆盖(不局限于二分图)
- 定义:在一个有向图中,用最少的互不相交的路径(无公共点),将所有点覆盖。
- 二分图中的性质:有向图中的最小路径覆盖数 = 点数 - 最大匹配数
证明
过程:
1. 拆点:将原图中每个点i作为左部拆出一个i'作为右部。并根据实际的路径图按照左出右入方式进行连边。
得到的性质:
1. 原图中的一个路径 --> 新图中的一个匹配,这一点很显然(拆完点后每条边的端点分别位于左右两边)
2. 原图中每条路径的终点(没有出边) --> 新图中,左部的一个非匹配点。因为路径终点不在向外连边故没有出边。
3. 除原图中的孤立点和终点外,新图中左部点的出度为1,右部入度为1.
问题转化:
1. 路径最少,终点最少,左部的非匹配点最少 n - m
--> 2. 左部的匹配点最多 m
--> 3. 找左部最大匹配 m
扩展:求DAG的最小路径重复点覆盖(路径间可以有公共点)
- 定义:选取最少可相交的边覆盖全部顶点
- 方法:
(1) 求出原图G的传递闭包G’。
(2) 在G’中求最小路径覆盖。
结论: DAG的最小路径重复点覆盖 = 传递闭包G’的最小路径覆盖。
证明:
过程:
1. 在G'中按照G的路径,从第一条路径开始走,若路径上有之前经过的点,则直接跳过
2. 直至走完所有的路径。
等价性证明:
(1) G -> G' :必然不会有某一条路径上所有的点均在之前被走过,
若有这样的路径,则路径重复,可以直接删除。
(2) G' -> G :直接展开过程1跳过的点。
所有原G路径数等于新图G'的路径数
关于最小路径覆盖(不可相交覆盖)最小路径重复覆盖(可相交覆盖)之间的关系
- 可相交覆盖的数目要<=不可相交覆盖(注:一个点可以单独作为一条路径)
举例:
关于本题思路(重点)
1. 首先问题要求尽可能多的藏身点组成集合,使得任意两点之间没有边。
这跟最小重复路径覆盖有关系吗?这不应该是最大独立集吗?经仔细查阅发现对于有向图是不可行的,必须是无向图才可用最大独立集。
好在天无绝人之路,题目中说视线可以沿着路径无限延展,似乎在引导我们往传递闭包上想。
2. 根据上面发现:可相交覆盖<=不可相交覆盖,那么为什么在求数目最多的情况下还要用可相交覆盖呢?
视线限制我们必须建立传递闭包,并在传递闭包上做不可相交覆盖。
这里看一下上图会发现,按照不可相交的路径数目是3,显然不论怎么选总会有前面可以看到后面
做完传递闭包后,按照不可相交的路径数目是2,是可行的。
证明处参考
答案==最小重复路径覆盖cnt
(1) 证≤cnt:
由于cnt条路径把所有点全覆盖了
1 所以选k个点从这cnt条路径上选
2 每条路径上不能选≥2个点 最多只能选1个点
否则一条路径上前面的点一定能看到后面的点(矛盾)
3 则答案必然≤cnt(最多cnt条路线,每条路线最多选1个,最多选cnt个点)
(2) 证≥cnt:
构造:
cnt条路线的cnt个终点放到集合E中
找一下这个E里面 每一个终点 所有可以到的点
next(E) : 从E中每个点出发可以到达所有点的集合
1. 如果E和next(E)无交集 说明E内的点两两之间不能互相到达 说明E中所有点就是一种方案(k=cnt)
2. 如果E和next(E)有交集
我们让终点E[i]沿有向边倒着走,走到E[i]不属于next(E)为止,直到做到E和next(E)没有交集为止
最多走到起点能达到E和next(E)没有交集
反证:
假设一直往前退到起点都不能保证E[i]不属于next(E)
则说明E[i]所在的起点(其他点都能被间接到达)都是E中所有终点(其他路径)能到达的
那这条路径就没有存在的价值了
可以找到能到达E[i]的路径path,把当前E[i]接到path后
E[i]作为起点的路径上的所有点都可以被覆盖,总路径数cnt-1
这就和cnt是最小路径重复点覆盖矛盾
所以答案就是cnt
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 210;
int n, m;
int g[N][N];
int match[N];
bool st[N];
bool find(int u) {
for (int i = 1; i <= n; ++i)
if (g[u][i]) {
if (st[i]) continue;
st[i] = true;
if (!match[i] || find(match[i])) {
match[i] = u;
return true;
}
}
return false;
}
int main() {
cin >> n >> m;
for (int i = 1; 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, 0, sizeof st);
if (find(i)) res++;
}
printf("%d\n", n - res);
return 0;
}
请问一下:为什么 显然不论怎么选总会有前面可以看到后面?
很抱歉 好久没敲 有点忘了 二分图这块涉及的前置知识比较多
建议根据y总的视频仔细看一下各个名词的定义,再比较一下当中的性质。由于考研在即,近期大概没有时间去弄懂这些
嗯好滴谢谢~~~