P96864

4.2.1 Drainage Ditches 草地排水

难度 未定
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

在农夫约翰的农场上,每逢下雨,贝茜最喜欢的三叶草地就积聚了一潭水.这意味着草地被水淹没了, 并且小草要继续生长还要花相当长一段时间.因此,农夫约翰修建了一套排水系统来使贝茜的草地 免除被大水淹没的烦恼(不用担心,雨水会流向附近的一条小溪).作为一名一流的技师,农夫约翰已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量.

农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局(起点为水潭而终点为小溪的一张网).需要注意的是,有些时候从一处到另一处不只有一条排水沟.

根据这些信息,计算从水潭排水到小溪的最大流量.对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形.

输入

第1行: 两个用空格分开的整数N(0<=N<=200) 和 M(2<=M<=200).N是农夫约翰已经挖好的排水沟的数量,M是排水沟交叉点的数量.交点1是水潭,交点M是小溪.

第二行到第 N+1行: 每行有三个整数,Si, Ei, 和 Ci.Si 和 Ei (1 <= Si, Ei <= M)指明排水沟两端的交点,雨水从 Si流向 Ei.Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量.

输出

输出一个整数,即排水的最大流量.

样例

样例 1
输入
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
输出
50

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交