P1343 地震逃生

    • 839通过
    • 2.6K提交
  • 题目提供者 yeszy 管理员
  • 评测方式 云端评测
  • 标签 图论 搜索 最大流 福建省历届夏令营
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    汶川地震发生时,四川**中学正在上课,一看地震发生,老师们立刻带领x名学生逃跑,整个学校可以抽象地看成一个有向图,图中有n个点,m条边。1号点为教室,n号点为安全地带,每条边都只能容纳一定量的学生,超过楼就要倒塌,由于人数太多,校长决定让同学们分成几批逃生,只有第一批学生全部逃生完毕后,第二批学生才能从1号点出发逃生,现在请你帮校长算算,每批最多能运出多少个学生,x名学生分几批才能运完。

    输入输出格式

    输入格式:

    第一行3个整数n,m,x(x<2^31,n<=200,m<=2000);以下m行,每行三个整数a,b,c(a1,a<>b,0描述一条边,分别代表从a点到b点有一条边,且可容纳c名学生。

    输出格式:

    两个整数,分别表示每批最多能运出多少个学生,x名学生分几批才能运完。如果无法到达目的地(n号点)则输出“Orz Ni Jinan Saint Cow!”

    输入输出样例

    输入样例#1: 复制
    6 7 7
    1 2 1
    1 4 2
    2 3 1
    4 5 1
    4 3 1
    3 6 2
    5 6 1
    输出样例#1: 复制
    3 3

    说明

    【注释】

    比如有图

    1 2 100

    2 3 1

    100个学生先冲到2号点,然后1个1个慢慢沿2-3边走过去

    18神牛规定这样是不可以的……

    也就是说,每批学生必须同时从起点出发,并且同时到达终点

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