P2764 最小路径覆盖问题

    • 1.5K通过
    • 3.1K提交
  • 题目提供者 yyy2015c01 嘤嘤嘤
  • 评测方式 云端评测
  • 标签 网络流 网络流24题 O2优化 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    提示:设 $V=\{1,2,...,n\}$ ,构造网络 $G_1=\{V_1,E_1\}$ 如下:

    $$V_1=\{x_0,x_1,...,x_n\}\cup\{y_0,y_1,...,y_n\}$$

    $$E_1=\{(x_0,x_i):i\in V\}\cup\{(y_i,y_0):i\in V\}\cup\{(x_i,y_j):(i,j)\in E\}$$

    每条边的容量均为 $1$ ,求网络 $G_1$ 的 $(x_0,y_0)$ 最大流。

    输入输出格式

    输入格式:

    第一行有 $2$ 个正整数 $n$ 和 $m$ 。 $n$ 是给定$\text{GAP}$(有向无环图) $G$ 的顶点数, $m$ 是 $G$ 的边数。接下来的 $m$ 行,每行有两个正整数 $i$ 和 $j$ 表示一条有向边 $(i,j)$。

    输出格式:

    从第1 行开始,每行输出一条路径。文件的最后一行是最少路径数。

    输入输出样例

    输入样例#1: 复制
    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: 复制
    1 4 7 10 11
    2 5 8
    3 6 9
    3

    说明

    $1\leq n\leq 150,1\leq m\leq 6000$

    由@FlierKing提供SPJ

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。