AcWing 379.Vani和Cl2捉迷藏

题目链接: AcWing 379. 捉迷藏

题目大意:

给定一张 \(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‘\)

  1. 依次考虑左部每一个非匹配点 \(x_0\)
  2. \(x_0\) 出发,不断访问 \(x_0\)\(match[x_0‘]\)\(match[match[x_0‘]]...\) 直至到达一个左部点 \(y_0\) \(s.t.\) \(y_0‘\) 是非匹配点。
  3. \(G‘\) 中,节点 \(x_0\)\(y_0\) 以及刚才经过的点构成一条路径。

这样找到的所有路径就是 \(path\) 的方案之一,所有路径在 \(G‘\) 上是不相交的。

接下来构造 \(select\)

  1. 选出 \(path\) 中每条路径的终点 \(x_0\) ,构成一个集合 \(E\)
  2. 求出从 \(E\) 中节点出发,走一条边,到达的集合 \(next(E)\)
  3. 根据传递闭包的性质, \(G\) 中任意两个选取的点没有路径相连,等价于 \(G‘\) 中任意两个藏身点都没有边相连。因此,若 \(E\bigcap next(E)=0\) ,则 \(select=E\) 即为所求。
  4. 否则,考虑 \(E\bigcap next(E)\) 中的每一个节点 \(e\) ,沿着 \(e\) 所在的路径向上走,直到一个节点 \(e‘\notin next(E)\) 。从 \(E\) 中删除 \(e\) ,加入 \(e‘\)
  5. 对于修改后的集合 \(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;
}

AcWing 379.Vani和Cl2捉迷藏

上一篇:delphi中Message消息的使用方法


下一篇:C#常用设计模式