精华内容
下载资源
问答
  • 最小路径覆盖 Description 定义: 一个不含圈的有向图G中,G的一个路径覆盖是一个其结点不相交的路径集合P,图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束,且长度也为任意值,包括0。请...

    最小路径覆盖

    Description

    定义: 一个不含圈的有向图G中,G的一个路径覆盖是一个其结点不相交的路径集合P,图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束,且长度也为任意值,包括0。请你求任意一个不含圈的有向图G的最小路径覆盖数。

    提示:最小路径覆盖数=G的定点数-最小路径覆盖中的边数
    最小路径覆盖数=原图G的顶点数-二分图的最大匹配数

    Input

    t 表示有t组数据;n 表示n个顶点(n<=120);m 表示有m条边;
       接下来m行,每行有两个数 i,j表示一条有向边。

    Output

    最小路径覆盖数

    Sample Input

    2
    4
    3
    3 4
    1 3
    2 3
    3
    3
    1 3
    1 2
    2 3

    Sample Output

    2
    1

    解题思路

    这题就是一道最小路径覆盖模板题目

    最小路径覆盖
    在这里插入图片描述

    定义:在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。 最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。 最小不相交路径覆盖:每一条路径经过的顶点各不相同。如图,其最小路径覆盖数为3。即1->3>4,2,5。 最小可相交路径覆盖:每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1->3->4,2->3>5。 特别的,每个点自己也可以称为是路径覆盖,只不过路径的长度是0。

    什么是有向图G的最小路径覆盖?首先,图G必须是有向无环的。路径覆盖就是在图G中找出一些路径,每条路径从起点走到终点并且标记中间经过的点。最后,每个点只被标记一次。选出的这些路径组成路径覆盖。如果找出最少的路径成为一个路径覆盖,则称为最小路径覆盖。

    在这里插入图片描述

    在上图中,以下两个均是路径覆盖: a、<1,2> <4,6> <3> <5> b、<1,2,4,6> <3> <5> 在上面两个覆盖中b为最小覆盖,|b|=3,而|a|=4。(注意一个单独的节点也是一个路径)

    由原图G构造对应的二分图S,将原图G中的每个点i拆成两个点i1和i2,i1和i2属于S。i1组成二分图的X集合,i2组成Y集合。若原图G中有边<i,j>,则在S中有边<i1,j2>,则上面的图可以得到如下二分图: 法:把原图的每个点V拆成Vx和Vy两个点, 如果有一条有向边A->B,那么就加边Ax−>By 。这样就得到了一个二分图。 那么最小路径覆盖=原图的结点数-新图的最大匹配数。
    在这里插入图片描述
    证明:一开始每个点都是独立的为一条路径,总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径,也就相当于路径数减少了1。所以找到了几条匹配边,路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。 因为路径之间不能有公共点,所以加的边之间也不能有公共点,这就是匹配的定义。

    AC代码

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    long long n,m,T,x,y,tot,answer,head[1005],cover[1005],father[1005];
    struct node//结构体
    {
    	long long to,next;
    }a[1000005];
    void add(long long x,long long y)//邻接表
    {
    	a[++tot]=(node){y,head[x]};
    	head[x]=tot;
    }
    bool dfs(long long x)//dfs
    {
    	if(x==0)return true;
    	for(long long i=head[x];i;i=a[i].next)
    	 if(cover[a[i].to]==0)
    	 {
    	 	cover[a[i].to]=1;
    	 	long long sum=father[a[i].to];
    		father[a[i].to]=x;
    	 	if(sum==0||dfs(sum))return true;
    	 	father[a[i].to]=sum;
    	 }
    	return false;
    }
    int main()
    {
    	scanf("%lld",&T);
    	while(T--)
    	{
    		tot=answer=0;//清零
    		memset(head,0,sizeof(head));
    		memset(father,0,sizeof(father));
    		scanf("%lld%lld",&n,&m);
    		for(long long i=1;i<=m;i++)
    		{
    			scanf("%lld%lld",&x,&y);
    			add(x,y);//建边
    		}
    		for(long long i=1;i<=n;i++)//匈牙利算法
    		{
    			memset(cover,0,sizeof(cover));
    			dfs(i);
    		}
    		for(long long i=1;i<=n;i++)
    	 	 if(father[i]!=0)answer++;
    		printf("%lld\n",n-answer);
    	}
    	return 0; 
    }
    

    谢谢

    展开全文
  • 最小路径覆盖

    千次阅读 多人点赞 2018-08-24 10:37:48
    花了好长时间,用于找了几篇能看懂的最小路径覆盖。 定义:通俗点将,就是在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。 最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。 最小不...

    花了好长时间,用于找了几篇能看懂的最小路径覆盖。

     

    定义:通俗点将,就是在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。

    最小路径覆盖分为最小不相交路径覆盖最小可相交路径覆盖

    最小不相交路径覆盖:每一条路径经过的顶点各不相同。如图,其最小路径覆盖数为3。即1->3>4,2,5。

    最小可相交路径覆盖:每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1->3->4,2->3>5。

    特别的,每个点自己也可以称为是路径覆盖,只不过路径的长度是0。

     

    大家要仔细想想上面的解释啊,这已经是我找到的最浅显的了。

    而且一定要知道有这两种最小路径覆盖。

    然后如果大家不知道匈利亚算法的,一定要去看看,还是比较简单的,就是一个dfs,连我都看的懂。

    下面地址是关于匈利亚算法的详解,带图解,易懂

    https://blog.csdn.net/Arabic1666/article/details/79824390

    DAG的最小不相交路径覆盖

    算法:把原图的每个点V拆成VxVx和VyVy两个点,如果有一条有向边A->B,那么就加边Ax−>ByAx−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。

    证明:一开始每个点都是独立的为一条路径,总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径,也就相当于路径数减少了1。所以找到了几条匹配边,路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

    因为路径之间不能有公共点,所以加的边之间也不能有公共点,这就是匹配的定义。

    说的拆点这么高深,其实操作起来超级超级简单,甚至没有操作。

    简单的来说,每个顶点都能当成二分图中作为起点的顶点。

    至于为什么答案是 n-ans,我谈谈我的理解

    用dfs求的ans表示的意思是匹配数,换句话说,就是一条路连着的路径上的点的个数-1

    比如说这个图,我们用匈牙利算法,遍历每个点,发现1、3点可行,可匹配,而2、4、5都不能行。

    如果我们单纯考虑1->3->5这条路径,有三个点,然后有两个点匹配了,我们用3减去2,就得到了1,这个1就是一个路径数,需要用1条路径来覆盖,再对剩下的2、4考虑,分别都需要一条路径来覆盖,因为2-0=0,2是顶点个数,0是匹配数。

    所以,对于每条分路径,我们需要 v-cnt的路径来覆盖,最后将每个分路径合起来,我们得到n-cnt。

    例题:POJ1422

     

    //
    //  main.cpp
    //  POJ1422最小不想交路径覆盖
    
    
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <vector>
    using namespace std;
    const int N = 200 + 10;
    vector<int> g[N];
    int cy[N];
    bool vis[N];
    bool dfs(int u)
    {
        for(int i=0; i<g[u].size(); ++i)
        {
            int v = g[u][i];
            if(vis[v]) continue;
            vis[v] = true;
            if(cy[v]==-1 || dfs(cy[v])){
                cy[v] = u;
                return true;
            }
        }
        return false;
    }
    int solve(int n)
    {
        int ret = 0;
        memset(cy, -1, sizeof(cy));
        for(int i=1;i<=n;++i)
        {
            memset(vis, 0, sizeof(vis));
            ret += dfs(i);
        }
        return n - ret;
    }
    int main( )
    {
        int t,n,m;
        int u,v;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;++i)
                g[i].clear();
            for(int i=0;i<m;++i)
            {
                scanf("%d%d",&u,&v);
                g[u].push_back(v);
            }
            
            int ans = solve(n);
            printf("%d\n",ans);
        }
        return 0;
    }

     

     

    DAG的最小可相交路径覆盖

    算法:先用floyd求出原图的传递闭包,即如果a到b有路径,那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

    证明:为了连通两个点,某条路径可能经过其它路径的中间点。比如1->3->4,2->4->5。但是如果两个点a和b是连通的,只不过中间需要经过其它的点,那么可以在这两个点之间加边,那么a就可以直达b,不必经过中点的,那么就转化成了最小不相交路径覆盖。

    上面的解释很不错,点个赞!

    题目POJ2594

    //
    //  main.cpp
    //  POJ2594最小可相交路径覆盖
    //
    //  Created by beMaster on 16/4/8.
    //  Copyright © 2016年 beMaster. All rights reserved.
    //
    
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <vector>
    using namespace std;
    const int N = 500 + 10;
    bool dis[N][N];
    bool vis[N];
    int cy[N];
    void floyd(int n){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                for(int k=1;k<=n;++k)
                    if(dis[i][k] && dis[k][j])//传递可达性
                        dis[i][j] = true;
    }
    bool dfs(int u, int n){
        for(int i=1;i<=n;++i){
            if(!vis[i] && dis[u][i]){
                vis[i] = true;
                if(cy[i]==-1 || dfs(cy[i], n)){
                    cy[i] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int solve(int n){
        int cnt = 0;
        memset(cy,-1,sizeof(cy));
        for(int i=1;i<=n;++i){
            memset(vis,0,sizeof(vis));
            cnt += dfs(i, n);
        }
        return n - cnt;
    }
    int main( ) {
        int n,m;
        int a,b;
        while(scanf("%d%d",&n,&m),n+m){
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    dis[i][j] = false;
            for(int i=1;i<=m;++i){
                scanf("%d%d",&a,&b);
                dis[a][b] = true;
            }
            floyd(n);
            int ans = solve(n);
            printf("%d\n",ans);
        }
        return 0;
    }

     

    做完这两道例题,可以做做我拉的题目啊,欢迎欢迎

    https://vjudge.net/contest/249592#problem

     

    展开全文
  • Java实现 LeetCode 64 最小路径

    万次阅读 多人点赞 2020-02-16 12:15:39
    64. 最小路径和 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 ...

    64. 最小路径和

    给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

    说明:每次只能向下或者向右移动一步。

    示例:

    输入:
    [
    [1,3,1],
    [1,5,1],
    [4,2,1]
    ]
    输出: 7
    解释: 因为路径 1→3→1→1→1 的总和最小。

    class Solution {
         public int minPathSum(int[][] grid) {
            if (grid == null || grid.length < 1 || grid[0] == null || grid[0].length < 1) {
                return 0;
            }
            
            int row = grid.length;
            int col = grid[row - 1].length;
            
            int dp[][] = new int[row][col];
            
            dp[0][0] = grid[0][0];
            
            for (int i = 1;i < row;i++) {
                dp[i][0] = dp[i - 1][0] + grid[i][0];
            }
            
            for (int i = 1;i < col;i++) {
                dp[0][i] = dp[0][i - 1] + grid[0][i];
            }
            
            for (int i = 1;i < row;i++) {
                for (int j = 1;j < col;j++) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
            
            return dp[row - 1][col - 1];
        }
    }
    
    展开全文
  • Java实现 LeetCode 120 三角形最小路径

    万次阅读 多人点赞 2020-02-19 15:59:22
    120. 三角形最小路径和 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 +...

    120. 三角形最小路径和

    给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

    例如,给定三角形:

    [
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]
    

    自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

    说明:

    如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

    class Solution {
         public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0){
                return 0;
            }
            // 只需要记录每一层的最小值即可
            int[] dp = new int[triangle.size()+1];
    
            for (int i = triangle.size() - 1; i >= 0; i--) {
                List<Integer> curTr = triangle.get(i);
                for (int j = 0; j < curTr.size(); j++) {
                    //这里的dp[j] 使用的时候默认是上一层的,赋值之后变成当前层
                    dp[j] = Math.min(dp[j],dp[j+1]) + curTr.get(j);
                }
            }
            return dp[0];
        }
    }
    
    展开全文
  • 最小路径覆盖详解

    千次阅读 2019-08-07 11:14:12
    最小路径覆盖又分为:最小不相交路径覆盖 和 最小可相交路径覆盖。 最小不相交路径覆盖 : 就是我们找到的每条路径不能相交,就是每条路径不能有同一个点。 最小可相交路径覆盖 : 这个与上面相对应,就是可以相交...
  • Leetcode 最小路径

    2021-02-13 08:34:30
    最小路径和 题目描述: 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 提示:    m == grid....
  • leetcode120. 三角形最小路径

    千次阅读 多人点赞 2019-12-31 17:35:11
    给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为11(即,2+3+5+1= 11)。 说明: 如果...
  • Leetcode 64. 最小路径

    千次阅读 2020-05-31 20:46:50
    最小路径和1、问题分析2、问题解决3、总结 1、问题分析 题目链接:https://leetcode-cn.com/problems/minimum-path-sum/   本质上就是一个动态规划问题。代码我已经进行了详细的注释,理解应该没有问题,读者可以...
  • 二叉树--最小路径

    千次阅读 2016-05-24 15:36:02
    最小路径二叉树中的最小路径指的是,二叉树中根节点到达叶子节点的路径中,距离最短的一个。//recursively public int minDepth1(TreeNode root) { if (root == null) { return 0; } else if (root.left != null ...
  • leetcode 64 最小路径

    千次阅读 2020-07-03 17:45:00
    题干: 给定一个包含非负整数的 m x n 网格,请找出一条从...以该矩阵为例,若想知道该矩阵到4的最小路径,其实只需要对比2,3哪个更小即可,选择小的那边,因此可以使用动态规划。 动态规划的三步: 1.状态定义: 假
  • 二叉树的最小路径

    千次阅读 2018-11-10 10:07:46
    二叉树的最小路径 描述 给一棵结点带权(权值各不相同,都是小于1000的正整数)的二叉树的中序和后序遍历,找一个叶子使得它到根的路径上的权值和最小。如果有多解,该叶子本身的权值应该尽量小。 输入 输入包含多组...
  • 动态规划-最小路径

    千次阅读 2018-07-24 15:43:17
    给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动...这是一道典型的动态规划题,用dp[i][j]表示从0点到[i][j]的最小路径和...
  • 动态规划之矩阵的最小路径

    千次阅读 2018-09-10 23:25:41
    题目:给定一个m*n的矩阵,从左上角开始,每次只能向下或向右走,最后到达右下角的位置,路径上所有数字加起来就是路径的和,返回所有路径中最小...路径 1--3---1--0--6---1---0是最小路径最小路径和是12,那么怎...
  • 矩阵的最小路径

    2019-06-30 16:44:12
    给定一个矩阵matrix,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中的最小路径和。 如果给定的矩阵matrix如下: 其中路径1,3,1,0,6,1,0...
  • Air Raid + Treasure Exploration 最小边覆盖: 最小路径覆盖: 有向无环图->二分图 传递闭包
  • 求解三角形最小路径问题 一、【问题描述】: 给定 高度为n的一个整数三角形,找出从顶部到底部的最小路径和,只能向先移动相邻的结点。首先输入n,接下来的1~n行,第i行输入i个整数,输出分为2行,第一行为最小路径,...
  • Leetcode64:最小路径

    2020-10-10 10:09:29
    Leetcode64:最小路径和 给定一个包含非负整数的mxn网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1...
  • 矩阵最小路径和练习

    千次阅读 2017-03-02 22:08:03
    给定一个矩阵map及它的行数n和列数m,请返回最小路径和。保证行列数均小于等于100.测试样例: [[1,2,3],[1,1,1]],2,3 返回:4这个也不难,对于格子中的每一个点,走到这一个点的最短路径只有两种情况,从上面下
  • 首先输入n,接下来的1~n行,第i行输入i个整数,输出分为2行,第一行为最小路径,第2行为最小路径和。 例如,下图是一个n=4的三角形,输出的路径是2 3 5 3,最小路径和是13。 问题求解 将三角形采用二维数组a存放,...
  • 图算法-最小路径

    2015-05-13 12:47:24
    1、单源最小路径之Dijkstra算法 void ShortestPath_Dijkstra(int startVertexNum, int[] shortestPath, int[] shortestDistance)//根据Dijkstra法计算距离指定顶点的最短路径 { bool[] isDone=new bool...
  • C/C++描述 LeetCode 120. 三角形最小路径

    千次阅读 多人点赞 2020-07-14 07:34:13
    三角形最小路径和   大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博主目前仅在CSDN中写博客,唯一博客更新的地址为:亓官劼的博客 本文原创为亓官劼,请...
  • 动态规划算法--矩形最小路径

    万次阅读 2020-07-05 23:00:18
    题目:给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小,每次只能向...求左上到右下的最小路径和,看来又一个累加问题,可以从局部最小和到整体最小和。为了方便...
  • 写这篇博客有两个原因,一是由于网上对这些结论的解释和证明太模糊,有些甚至是错的(有的人没分清楚最小路径覆盖和最小边覆盖,用错误的证明来推出结论)。二也是为了纪念人生头一次区域赛没拿奖吧(少做的一道题就是...
  • 有向图的最小路径覆盖(所有点)可以用二分图来解,n-最大匹配。 无向图的最小路径覆盖(所有点)似乎是比较困难的问题 那么对于特殊的无向图 - '树'来说,求它的最小路径覆盖有什么好用的方法呢? 首先我们可以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 436,748
精华内容 174,699
关键字:

最小路径