TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1938
  • 题目
  • P1938【线性规划与网络流24题 3】最小路径覆盖
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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

    提示:设V={1,2,... ,n},构造网络 G1=(V1,E1)如下:
    V1 = { x0, x1, ..., xn} U { y0, y1, ..., yn} ,
    E1 = {(x0,xi):i包含于V} U {(yi,y0):i包含于V} U {(xi,yj):(i,j)包含于E}
    每条边的容量均为1。求网络G1 的(x0,y0 )最大流。


    对于给定的给定有向无环图G,编程找出 G的一个最小路径覆盖。

    由于本OJ无Special Judge , 所以只需要输出路径的条数

    输入格式

    第1 行有 2个正整数 n和 m。n是给定有向无环图(0<n<=150,0<=m<=n*n)
    G 的顶点数, m是G 的边数。 接下来的 m行, 每行有 2 个正整数 i和 j, 表示一条有向边(i,j)。

    输出格式

    /
    程序运行结束时,将最小路径覆盖输出。
    从第 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 4 7 10 11
    2 5 8
    3 6 9
    */
    3

    提示

    无视被/* */包括的内容


    来源  感谢 Wo_ai_WangYuan 修改题目并放上数据