博客链接: AcWing 379.Vani和Cl2捉迷藏
题目大意:
给定一张 $N$ 个点,$M$ 条边的有向无环图,求最多能选取的点数 $K$,使得选取的任意两点都没有路径相连。
$N\leq 200, M\leq 30000$
思路:
可以发现选取的点是路径的起点时最保险的,这时该点不能从任何地方到达,这样我们注意到一条路径上其实最多只能选取一个点,则 $|select|\leq |path|$,在所有的路径方案中,有一个最低的上限,即最小路径可重复点覆盖的大小,下面用 $path$ 表示该情况的边集。
接下来尝试构造 $|select|=|path|$ 的取点,若方案存在,则答案 $K$ 即为 $|path|$ 。
对原图 $G$ 进行传递闭包,得到新的 $DAG$ $G’$,首先构造 $path$ 的具体方案:
路径覆盖包含的路径条数最少
$\iff$ 路径终点数(出度为 $0$ 的点数)最少
$\iff$ $(x,y) \Rightarrow (x,y+n)$ 构造的拆点二分图 $G_2’$ 左部非匹配点最少 (二分图具体可以参考这一篇)
在最优情况下,每一条路径的起点入度和终点出度必然为零,设节点 $x\in G’$ 在 $G_2’$ 中对应左部点 $x$ 和 $x’$ :
- 依次考虑左部每一个非匹配点 $x_0$ 。
- 从 $x_0$ 出发,不断访问 $x_0$ ,$match[x_0’]$ ,$match[match[x_0’]]…$ 直至到达一个左部点 $y_0$ $s.t.$ $y_0’$ 是非匹配点。
- 在 $G’$ 中,节点 $x_0$,$y_0$ 以及刚才经过的点构成一条路径。
这样找到的所有路径就是 $path$ 的方案之一,所有路径在 $G’$ 上是不相交的。
接下来构造 $select$ :
- 选出 $path$ 中每条路径的终点 $x_0$ ,构成一个集合 $E$ 。
- 求出从 $E$ 中节点出发,走一条边,到达的集合 $next(E)$ 。
- 根据传递闭包的性质, $G$ 中任意两个选取的点没有路径相连,等价于 $G’$ 中任意两个藏身点都没有边相连。因此,若 $E\bigcap next(E)=0$ ,则 $select=E$ 即为所求。
- 否则,考虑 $E\bigcap next(E)$ 中的每一个节点 $e$ ,沿着 $e$ 所在的路径向上走,直到一个节点 $e’\notin next(E)$ 。从 $E$ 中删除 $e$ ,加入 $e’$ 。
- 对于修改后的集合 $E$ ,重复执行步骤 $3$ 和 $4$ ,直到步骤 $3$ 中的条件满足。
可以证明,任何时刻在步骤 $4$ 中,我们一定能找到合法的 $e’$ 。这是因为如果找不到这样的 $e’$,就说明 $e$ 所在的路径(记为 $pe$)上的所有点都能够被其他路径的终点到达。设 $pe$ 的起点是 $y_0$,我们可以延长那条到达 $y_0$ 的路径,代替 $pe$ 去覆盖 $pe$ 上的所有节点,使集合 $path$ 中的路径减少一条,与 $path$ 的最小性矛盾。
你认为这道题做完了?并没有。手头有《算法竞赛进阶指南》的读者可以发现这段构造和反证跟书上的文字一模一样,如果你仔细去思考一下这个反证,与我尝试解释去解释它的时候一样,会发现这是有逻辑漏洞的。
这个反证法的说明其实只适用于第一个要找的 $e’$,对于后面的调整, $next(E)$ 中不仅仅有终点的相连点了,还有已经调整好的点的相连点。也就是说,此时这个路径不一定能被完全替代,别的路径走过来可能需要在中间拐个岔子,而不是到了终点再往这条路径上走。
不过这个构造是无懈可击的,题目后面其实有一个更加深刻的东西支撑其正确性:
$Dilworth$ 定理:对偏序集 < A,≤ > ,设A中最长链的长度是n,则将A中元素分成不相交的反链,反链个数至少是n。
这个定理可以说明对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目,而最大反链大小即为此题所求的 $K$ 。其证明可以在网上查到,其中与图论紧密相连的有这一篇。
身为中学生,个人知识水平有限,不能进一步延伸,比较感兴趣的就自己上网了解一下吧。。
实现
对原图进行传递闭包,然后求出拆点二分图的最大匹配,答案即为 $N$ 减去最大匹配数,时间复杂度 $O(N^3)$ 。
由于二分图实际上只遍历其中一边,所以二分图不拆点跑匈牙利是不影响正确性的。
Code:
#include<iostream>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define N 220
using namespace std;
bool conn[N][N],vis[N];
int match[N],n;
bool dfs(int x){
rep(y,1,n)if(conn[x][y]){
if(vis[y])continue;
vis[y]=true;
if(!match[y]||dfs(match[y])){
match[y]=x; return true;
}
}
return false;
}
int main(){
int m,a,b;
cin>>n>>m;
rep(i,1,m){
cin>>a>>b; conn[a][b]=true;
}
rep(k,1,n)rep(i,1,n)rep(j,1,n)
conn[i][j]|=conn[i][k]&conn[k][j];
int ans=n;
rep(i,1,n){
memset(vis,false,sizeof(vis));
ans-=dfs(i);
}
cout<<ans;
return 0;
}
楼主说的逻辑漏洞应该指的是当点e不断上移的过程中,路径上的点e’的next(e’)也加入到了next(E)中;
但其实书上的分析是没错的,next(E)指的是E走一步能到达的点集合,前提是E,然后再是next(E);
书上说从E中删除e,然后加入e’,这时的next(E)并不包含原来的next(e),而是将之替换为了next(e’),所以书上的证明是没错的;
但是书上的代码并不如我上面的分析一样,更像是楼主分析的逻辑漏洞,因此我将书上的代码进行了修改,如下所示:
当你取消注释在原题数据集上跑的时候能AC,并不会输出”false”,说明确实找到了正确的隐藏点。
$\text{next}(e^{‘})$肯定是$\text{next}(e)$的超集,所以你的代码里面
if (d[i][j]) vis[j]--;
是无效的,后面的if (d[i][j]) vis[j]++;
会加回来也就是书上的分析确实有问题
!!!终于找到有同样想法的人了, 我就感觉书上说的不太对
大佬nb, 我也感觉书上的有点不对, 但自己又不会证明, 看完dilworth定理终于懂了
纯菜鸡,今天看到这里想不懂,原题不是让我们求最多可躲藏点数量吗,每个路径都只有一个点能成为答案,那为什么求的不是最多路径条数,而是最少路径覆盖呢
求最多可躲藏点数量,每个路径是最多有一个点能成为答案。 具有偏序性质的dag中,最小路径覆盖等于最大独立集
,所以我们求最小路径覆盖
挑战权威需要一点勇气,哪里写错了一定要指出来呀
您在文中提到,“构造无懈可击”是不是有问题呀,构造应该就有问题吧,因为逻辑漏洞;但是可以用Dilworth定理说明答案的确是传递闭包的最小路径覆盖