洛谷 P1343 地震逃生问题（最大流dinic算法）

地震逃生

题目描述

在汶川地震发生之际（情景描写），一所四川中学正在进行课程教学（场景描述）。当余震初起（时间点），学生们纷纷慌乱逃窜（动作描写）。该校的教学楼布局可被建模为一个有向图（技术术语），其中节点代表教室与安全区域（具体场所），边则表示连接通道（连接关系）。具体来说（详细说明），教室位于节点1号位置（位置标记），而安全地带则设于节点n号位置（目标定位）。通道具有容量限制特征（属性描述），一旦超过承载能力就可能引发 Structure collapse （结果预测）。在这种情况下（疑问引入），学校校长面临一个关键决策：如何组织学生疏散以最大限度减少伤亡。（问题提出）目前的问题是：每批逃生中最多能运送多少学生？现有x名学生需要分成几批撤离？每一批必须等上一批撤离完毕后才能开始撤离行动。（问题拆解）

输入格式

第一行给出三个整数值 n, m, x；接下来的每一行中包含三个整数值 a, b, c（满足条件：1≤a,b≤n 和 0≤c≤x），其中每一个a-bc表示从a点到b点有一条边，并且这条边可容纳的学生数量为c名。

输出格式

一对整数各自代表每个批次最多可运送的学生数量。将x名学生分成若干批次完成运输任务。若未能抵达指定地点（记为n号点），则程序应返回指定错误信息字符串 `Orz Ni Jinan Sai