最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 最小路径覆盖

    正文概述 陈老师   2026-01-20 15:15:01  

    题目描述

    给定有向图 G=(V,E)G=(V,E) 。设 PP 是 GG 的一个简单路(顶点不相交)的集合。如果 VV 中每个顶点恰好在 PP 的一条路上,则称 PP 是 GG 的一个路径覆盖。PP 中路径可以从 VV 的任何一个定点开始,长度也是任意的,特别地,可以为 00。GG 的最小路径覆盖是 GG 所含路径条数最少的路径覆盖。设计一个有效算法求一个 DAG(有向无环图)GG 的最小路径覆盖。

    输入格式

    第一行有两个正整数 nn 和 mm。nn 是给定 DAG(有向无环图)GG 的顶点数,mm 是 GG 的边数。

    接下来的 mm 行,每行有两个正整数 ii 和 jj 表示一条有向边 (i,j)(i,j)。

    输出格式

    从第一行开始,每行输出一条路径。

    文件的最后一行是最少路径数。

    11 12
    1 2
    1 3
    1 4
    2 5
    3 6
    4 7
    5 8
    6 9
    7 10
    8 11
    9 11
    10 11
    
    1 4 7 10 11
    2 5 8
    3 6 9
    3
    

    说明/提示

    对于 100%100\% 的数据,1≤n≤2001\leq n\leq 200,1≤m≤60001\leq m\leq 6000。

    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 最小路径覆盖