USACO Training 4.2.1 Drainage Ditches 题解与分析（草地排水）<网络流DINIC算法>

Drainage Ditches 草地排水

---

描述

在农夫约翰所拥有的农场中，每当降雨降临，Bessie最为喜爱的三叶草草地便会形成一片积水区域。这不仅意味着草地被水淹没，还可能导致草地中的植物需要较长时间才能恢复生长。为了解决这一问题，农夫约翰设计并建立了一套排水系统，以确保贝茜的草地不再受到洪水的困扰（可以放心的是，雨水最终会流向附近的小溪）。作为一位技艺高超的工程师，农夫约翰在每条排水沟的两端都安装了控制装置，以便他能够调节进入排水沟的水流速度。

农夫约翰清楚地掌握了每条排水沟每分钟所能承载的最大水量以及整个排水系统的具体结构（该系统由起点为积水区域、终点为小溪的一张网络构成）。值得注意的是，在某些情况下，从一个地点到另一个地点可能存在多条不同的排水沟。

根据这些数据，请计算从积水区域向小溪排放雨水的最大流量。对于每条排水沟而言，雨水只能按照特定的方向流动，并且需要注意的是，在某些情况下可能会出现雨水循环流动的现象。

格式

PROGRAM NAME :ditch

INPUT FORMAT :

(file ditch.in)

第一行包含两个由空格分隔的整数N (0 <= N <= 200) 与 M (2 <= M <= 200)。其中N代表农夫John已挖掘完成的排水沟数目，M表示排水沟交汇点的总数。交汇点1为水潭，