#P1343. 地震逃生

    ID: 387 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>搜索图论福建省历届夏令营最大流

地震逃生

题目描述

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

输入格式

第一行三个整数 n,m,xn,m,x
以下 mm 行,每行三个整数 a,b,ca,b,c1a,bn1\leq a,b\leq n0cx0\leq c\leq x)描述一条边,分别代表从 aa 点到 bb 点有一条边,且可容纳 cc 名学生。

输出格式

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

6 7 7
1 2 1
1 4 2
2 3 1
4 5 1
4 3 1
3 6 2
5 6 1
3 3

提示

【注释】

比如有图

1 2 100
2 3 1

100100 个学生先冲到 22 号点,然后一个一个慢慢沿 232 \to 3 边走过去。

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

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

【数据范围】

对于 100%100 \% 的数据,0x<2310 \le x < 2^{31}1n2001 \le n \le 2001m20001 \le m \le 2000