为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/ditch
来自NOCOW
< USACO
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 4 .2中的OI题目Drainage Ditches的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
[编辑] 问题分析
很明显的网络最大流模型。用最普通的BFS找增广路都可以过。 但是这个图可能不是简单图，也就是说两点之间可能存在不止一条边，而且边的容量还不一定相同。这样对于邻接矩阵来说就有点问题了。 解决方法也很简单：增加一个点。 如果在读入的时候，给出的两个点x,y（边容量为r）之间已经存在一条边了，我们就增加一个点z，在x,z和z,y之间分别连一条边，并且容量均为r。这样做的效果就是：不影响结果，而且避免了很麻烦的计算。
（做到后面的题目时，发现这样还是麻烦，还有更简单的方法，就是读入的时候不是采取直接赋值，而是采取累加的方法。这样所有重复的边就等于是一条边，这条边的容量等于先前所有重复边的容量和。原来的方法更适用于比较复杂的处理，比如涉及到具体的边的时候）
最大流的算法也有很多，最原始的BFS，最短增广路算法，一般预流推进算法，以及更好的预流推进……我用的是highest relabel-to-front，效率相当高，所有数据全部是0s^_^。
(其实。。不论什么算法。。在USACO上基本上都是0s)
WinterLegend Says : 补充一点，题目中说要注意雨水环形流动的情形，这个其实是不必纳入考虑的，因为在环中，出的还是等于进的，容量守恒，所以整个点容量守恒。 在Preflow-Push中，这条loop不会有值，因为点自己和自己的高度相同。
来个人品算法：只统计源点能出发的流量和汇点能收到的流量，取最小值输出，只有2~3个点过不了…… by hc199581
