小指针

V1

2022/10/06阅读:32主题:凝夜紫

【图论专题】二分图中的最小路径点覆盖问题的求解思路

外部链接公众号无效,点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。

前置知识

图论基础之二分图中最小覆盖问题的求解思路

最小路径点覆盖

在一个有向无环图中,用最少的互不相交的路径将所有点覆盖,我们叫做最小路径点覆盖,又称为最小路径覆盖

拆点:把一个点拆分成两个点1,左边作为出点1,右边作为入点

经过如上拆点的过程之后,我们发现一条边i->j可以拆分成一条由i指向 的一条边,这样我们就得到了一个二分图。

为什么这样分成的图是二分图呢?

注意,我们的拆点规则,我们是把一个点分成两部分,边的出度总是在左边(左集合),边的入度总是在右边(右集合),也就是说不可能有边的两个端点全在左边或者全在右边的情况。

用上述的方式,我们将原图中的所有路径转化到新的二分图中,因为原图有性质路径都是互不相交的,也就是说原图中一个点只属于一条边

所以,转换到新图中就是一个点只有一个入度和一个出度,也就是说左部的每一个点只会向右部连接一条边,右侧的每一个点也只属于一条边

总结一下:

  1. 原图中每条路径 和 新图(二分图)中的每个匹配是一一对应关系;
  2. 还有一个隐藏的性质,原图中每个路径的终点 和 新图(二分图)中 左边的某个 非匹配点 是对应的

综上,根据上述两条性质,我们先把原问题求原图中最少的互不相交的路径数量等价变形成求互不相交的路径终点数量最少,等价于求左边非匹配点的数量最少,等价于求左边匹配点的数量最多(总点数减去匹配点就是非匹配点),而左侧每个匹配点都对应一个匹配,所以问题最终转换为求新图(二分图)的最大匹配数量

最小路径重复点覆盖

扩展概念,在上面的内容里,我们求的是用最少的互不相交的路径将所有点覆盖,所以称为最小路径点覆盖问题;那么取消掉互不相交这个条件,我们称为最小路径重复点覆盖问题

解决该扩展问题只需要两步:

  1. 在原图G上面求传递闭包,得到新图 。求传递闭包,相当于在原图上增加了很多边,比如:原来边1->2->3,则根据传递性增加一条边1->3

  2. 在新图 上求最小路径覆盖即可。

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的方案

  1. 集合E:我们找出cnt条路线的所有终点,总共有cnt个,把这些终点全部放到集合E中;

  2. next(E):这是一个函数,它的返回值是从E中的每个点出发,可以到达的所有点的集合

  3. 让E和next(E)取交集,则会出现两种情况:

    1. 两者交集为空集,说明我们从集合E的任何一个点出发,都不可能到达集合E内部的任何点,也就是说集合E里面的点是不能相互到达的,那么因为集合E里面总共有cnt个点,所以我们就构造出了一种方案K==cnt

    2. 两者的交集为非空集,从集合E中选择出某一个点ei,让ei一直沿着它的边往前走,直到走到ei不属于next(E)为止。对集合E中的每个ei都执行这种操作。全部执行完成之后就可以得到两者交集为空集的情况。

    3. 还存在一个问题,对于每个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, 0sizeof st);
        if (find(i)) res ++ ;
    }
    printf("%d", n - res); // 总点数 - 最大匹配点
    return 0;
}

END

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1