A22640.地震逃生
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
汶川地震发生时,四川**中学正在上课,一看地震发生,老师们立刻带领 x 名学生逃跑,整个学校可以抽象地看成一个有向图,图中有 n 个点,m 条边。1 号点为教室,n 号点为安全地带,每条边都只能容纳一定量的学生,超过楼就要倒塌,由于人数太多,校长决定让同学们分成几批逃生,只有第一批学生全部逃生完毕后,第二批学生才能从 1 号点出发逃生,现在请你帮校长算算,每批最多能运出多少个学生,x 名学生分几批才能运完。
输入格式
第一行三个整数 n,m,x;
以下 m 行,每行三个整数 a,b,c(1≤a,b≤n,0≤c≤x)描述一条边,分别代表从 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 号点,然后一个一个慢慢沿 2→3 边走过去。
18 神牛规定这样是不可以的……
也就是说,每批学生必须同时从起点出发,并且同时到达终点。
【数据范围】
对于 100% 的数据,0≤x<231,1≤n≤200,1≤m≤2000。