DAG最小路径点覆盖,最小路径可重复覆盖,详解

这篇具有很好参考价值的文章主要介绍了DAG最小路径点覆盖,最小路径可重复覆盖,详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

关于二分图:二分图及染色法判定

关于二分图最大匹配:二分图最大匹配——匈牙利算法详解

关于二分图带权最大完备匹配:二分图带权最大匹配-KM算法详解


有向无环图的最小路径点覆盖

概念

给定一张有向无环图,要求用尽量少的不相交的简单路径,覆盖有向无环图的所有顶点(也就是每个顶点恰好被覆盖一次)。这个问题被称为有向无环图的最小路径点覆盖,简称**“最小路径覆盖”**。

拆点二分图

设原来的有向无环图为G = (V , E), n = |V|。 把G中的每个点x拆成编号为x和x+n的两个点。建立一张新的二分图,1~n作为二分图左部点,n + 1 ~ 2n作为二分图右部点,对于原图的每条有向边(x,y), 在二分图的左部点x与右部点y+n之间连边。最终得到的二分图称为G的拆点二分图,记为G’。例如:

DAG最小路径点覆盖,最小路径可重复覆盖,详解,数据结构与算法,c++,数据结构,图论

定理

有向无环图G的最小路径点覆盖包含的路径条数,等于n减去拆点二分图G’的最大匹配数。

证明

在有向无环图G= (V,E)的最小路径覆盖中,对于任意的x ∈ V,因为路径不相交,所以x的入度和出度都不超过1。因为每个节点都被覆盖,所以x的入度和出度至少有一个是1
因此,最小路径覆盖中的所有边,在拆点二分图G‘中构成一组匹配。最小路径覆盖中每条边(x,y) 的起点x与拆点二分图每条匹配边(x,y+n)的左部点x是一一对应的
特别地,对于每条路径的终点t,因为t没有出边,所以在二分图中,t匹配失败。即路径的终点和拆点二分图左部的非匹配点是一一对应的。

故有:路径覆盖包含的路径条数最少

等价于 路径的终点数(出度为0的点数)最少

等价于 拆点二分图左部非匹配点最少

等价于 拆点二分图匹配数最大

G的最小路径覆盖的路径数等于n减去拆点二分图G‘的最大匹配数
证毕。

最小路径可重复覆盖

给定一张有向无环图,要求用尽量少的可相交的简单路径,覆盖有向无环图的所有顶点(也就是一个节点可以被覆盖多次)。这个问题被称为有向无环图的最小路径可重复点覆盖

解决策略

在最小路径可重复点覆盖中,若两条路径:…→u→p→v→…和…→x→p→y→…在点p相交,则我们在原图中添加一条边(x,y),让第二条路径直接走x→y,就可以避免重复覆盖点p。

进一步地,如果我们把原图中所有间接连通的点对x,y直接连上有向边(x,y),那么任何“有路径相交的点覆盖”一定都能转化成“没有路径相交的点覆盖”。实际上,转化后的拆点二分图的未匹配左部点仍为最小可相交路径数目,例如:DAG最小路径点覆盖,最小路径可重复覆盖,详解,数据结构与算法,c++,数据结构,图论

综上所述,有向无环图G的最小路径可重复点覆盖等价于先对有向图传递闭包得到有向无环图G’,再在G’上求一般的(路径不可相交的)最小路径点覆盖

代码实现

#define int long long
#define N 205

int n, m, match[N]{0}, ans = 0;
bool vis[N], g[N][N]{0};//邻接矩阵存图
//匈牙利
bool dfs(int u)
{
    for (int v = 1; v <= n; v++)
        if (!vis[v] && g[u][v])
        {
            vis[v] = true;
            if (!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    return false;
}

//main
    // Floyd求传递闭包
    for (int i = 1; i <= n; i++)
        g[i][i] = 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];

    for (int i = 1; i <= n; i++)
        g[i][i] = false;

    for (int i = 1; i <= n; i++)
        memset(vis, 0, sizeof(vis)), ans += dfs(i);

    cout << n - ans;

OJ练习

379. 捉迷藏 - AcWing题库

这道题目的最大藏身点数目就是给定的有向无环图的最小路径可重复覆盖数目。

设最大藏身点集合为hide,最小路径可重复覆盖为path,往证hide = path:

显然藏身点不能在同一条路径上,而path包含了所有的点,所以每条path最多选一个藏身点,故|hide| <= |path|

如果我们能在path上构造出|path|个藏身点,那么就得证了,因为|hide|是最大藏身点数目,而最大又不超过|path|。

求path很容易,我们即然能求出最小覆盖,自然能还原出路径:

  1. 对于每条path的终点即为拆点二分图非匹配点,这个显然很好求
  2. 非匹配点x的右部拆点为x + n,那么通过match[x + n]可以找到x在path的邻接点y,同样的方法一直往下进行,可以还原出path

问题在于如何从每条path上选出一个藏身点:

  1. 记path终点集合为E,从E发出的边往下走,访问到的节点集合为next(E)
  2. 若E ∩ next(E) = Ø,即藏身点之间无路径,那么E 可以作为 hide
  3. 否则,对于E ∩ next(E)中的 每个节点e,沿着路径往回走,总能找到e’ ∉ next(E),否则path数目会减少,和最小覆盖矛盾
  4. 找到e’后删除e,再重复3,直到E ∩ next(E) = Ø,此时E即为符合条件的hide

证毕

AC代码如下:文章来源地址https://www.toymoban.com/news/detail-798711.html

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <functional>
using namespace std;
#define int long long
#define N 205

int n, m, match[N]{0}, ans = 0;
bool vis[N], g[N][N]{0};

bool dfs(int u)
{
    for (int v = 1; v <= n; v++)
        if (!vis[v] && g[u][v])
        {
            vis[v] = true;
            if (!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    return false;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    //freopen("in.txt", "r", stdin);

    cin >> n >> m;
    for (int i = 0, a, b; i < m; i++)
    {
        cin >> a >> b;
        g[a][b] = true;
    }
    for (int i = 1; i <= n; i++)
        g[i][i] = 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];

    for (int i = 1; i <= n; i++)
        g[i][i] = false;

    for (int i = 1; i <= n; i++)
        memset(vis, 0, sizeof(vis)), ans += dfs(i);

    cout << n - ans;
    return 0;
}

到了这里,关于DAG最小路径点覆盖,最小路径可重复覆盖,详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构OJ:最小栈

    OJ链接 简而言之,题目就是要我们实现一个栈,这个栈能够快速查找最小值,要求时间复杂度O(1),也就是说不能循环暴力查找 思路: 也许很多人一看到这个题目就有思路,就是定义一个min变量,入栈的时候如果元素比min小就更新min 但是这么做会有一个问题,如果最小值被p

    2024年02月11日
    浏览(46)
  • 【数据结构OJ题】删除有序数组中的重复项

    原题链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 用 双指针算法, 定义两个变量src和dst,一开始让src和dst指向num[ ]数组的第一个元素,再使用if语句判断。 如果nums[src]==nums[dst],就让src指向下一位,即src++。如果nums[src]!=

    2024年02月14日
    浏览(39)
  • Java高阶数据结构 & 并查集 & 最小生成树

    并查集与最小生成树 1.1 并查集的原理 在一些应用问题中,我们常常会遇到一类问题 一开始是一个人 后来新增的人可能与这个人有关系,也可能与这个人无关系。 一个人与一个人有关系,这个人与另一个人也有关系,那么三人都有关系。 有关系的和没关系的之间是不同的类

    2024年02月03日
    浏览(40)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(38)
  • 【LeetCode: 155. 最小栈 + 栈 + 数据结构设计】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月22日
    浏览(56)
  • 数据结构——关键路径

    ——本节内容为Bilibili王道考研《数据结构》P67视频内容笔记。 目录 一、基本概念 1.AOE网 2.AOE网的性质  3.关键路径 4.最早最晚时间 二、求关键路径 1.步骤 2.举例 三、关键活动/路径特性 1.AOE网         在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表

    2024年02月07日
    浏览(42)
  • 【数据结构】树形结构所有路径复原为链表

    目录 1. 树形结构可视化 2. 树形结构转为链表 此目标是要还原树形结构的所有路径。树形结构是一种常见的数据结构,它表示元素之间层次关系。在树形结构中,每个节点可能拥有一个或多个子节点,形成了一个分层的结构。为了还原树形结构的路径,我们需要找到从根节点

    2024年02月06日
    浏览(34)
  • 数据结构--6.2关键路径

    AOE网:         在一个表示工程的带权有向图中,用顶点表示事件,用有向边上的权值表示活动表示持续时间,这种有向图的边表示活动的网,我们称为AOE网(Activity On Edge Network)。 我们把AOE网中没有入边的顶点称为始点或源点,没有出边的顶点称为终点或汇点。   ——

    2024年02月09日
    浏览(37)
  • 数据结构与算法课程设计---最小生成树的应用

    1.问题 假定有这么一个问题,有11个城市,城市之间有一些天然气管道,铺设天然气管道需要花费不同的金额,现在要你选择其中一些天然气管道,使得所有城市可以互相联通且花费最小。 2.分析 我们把这个问题抽象为一张图,每个城市是一个顶点,城市与城市之间的管道是

    2024年02月08日
    浏览(51)
  • 【数据结构课程设计】关键路径问题

    1 问题描述与功能需求分析 1.1问题描述 1) 任务:设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。 2)基本要求: (1)对一个描述工程的 AOE 网,应判断其是否能够顺利进行。 (2)若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及

    2024年02月10日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包