#P201. 「网络流模板」最大流
「网络流模板」最大流
Description
在 Farmer John 的农场上,每逢下雨,Bessie 最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间。因此,农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼(不用担心,雨水会流向附近的一条小溪)。作为一名一流的技师,农夫约翰已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量。
农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局(起点为水潭而终点为小溪的一张网)。需要注意的是,有些时候从一处到另一处不只有一条排水沟。
根据这些信息,计算从水潭排水到小溪的最大流量。对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形。
简要题意:给定一个 个点, 条边的带流量网络,求 到 的最大流。
Input Format
第一行两个用空格分开的整数 和 。 是农夫 John 已经挖好的排水沟的数量, 是排水沟交叉点的数量。交点 是水潭,交点 是小溪。
注意 (边数)在前 (点数)在后!
第二行到第 行:每行有三个整数,、 和 。
和 指明排水沟两端的交点,雨水从 流向 。 是这条排水沟的最大容量。
Output Format
输出一个整数,即排水的最大流量。
Sample
样例输入
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
样例输出
50
Hint
$ 0 \leq m \leq 200, 2 \leq n \leq 200, 1 \leq s_i, t_i \leq n, 0 \leq c_i \leq 10 ^ 7 $