为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/milk6
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 4 .4中的OI题目Pollutant Control的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 若风的算法
下面的每个多项式算法我感觉都有反例了，如果你相信的话，可以看看我的做法。有分析+证明+程序。 因为是作为解题报告而存在的，所以写的非常啰嗦（褒义词叫详细~~）。就不复制过来了……偶然发现原来的blog崩了。重发之http://hi.baidu.com/fmlzlkalohbcgod/item/f775ae07057d5cc0ff240d81
我的想法与这位同志差不多。
不要想复杂了。
只要把容量为c的边重赋权为c*1001+1，即可解决前两问。
再按编号从小往大的顺序枚举每条边，判断去掉之后最大流减小值是否等于边权。是则输出。 // 为什么要这样做? 直接从原点开始做一个floodfill 然后枚举每条边如果端点一个被访问过一个没有 不就可以判定这条边在最小割中么? --路人甲 // 个人认为路人甲的算法可以举出反例：满足题目条件的最小割可能不止一个，需要按字典序依次枚举 --路人乙
完全没有必要像下面某几位仁兄一样麻烦还错了（没有冒犯之意）。
[编辑] 正确的解法
具体的可以看这篇文章：http://bbs.noi.bdez.cn:8080/viewthread.php?tid=44&extra=page%3D1
代码流程：
s1 : 按编号顺序存边表L1。然后，按容量递减顺序(容量相等时，编号小的在前)mergesort，得到L2 s2 : HLPP求出最大流tot s3 : 按L2的顺序枚举边，如果该边的容量小于等于最大流tot，且删除该边后，再求一次得到的最大流与删除前的最大流之差等于该边容量，那么，该边一定属于最小割，删除它，否则就恢复。 s4 : 经s3删边后，最大流>0，那么剩下的边中仍有边属于最小割。我们可以按L1的顺序递归搜索，枚举每个边是不是属于最小割，并加入一些剪枝。 s5 : 求出最小割后，把要输出的边按标号countsort一下。
具体代码请进Pascal题解区或者上面的连接
个人认为此方法无法保证字典序最小。
这两个方法是错的吧？是我理解错了还是方法的错了？反正第一个程序应该是错的。 反例:
9 11 1 2 4 1 3 3 2 4 10 3 4 10 4 5 4 6 1 4 7 1 5 8 100 6 8 100 7 8 100 8 9 100
这组数据输出为：
7 2 1 2
再提供一组数据：
8 9 7 8 1 1 2 1 1 3 1 6 8 1 2 4 100 3 4 100 4 5 100 5 7 100 5 6 100
输出：
2 2 1 4
如果输出：
2 3 一般是因为使用了改权值的方法，只能保证和最小，不能保证字典序最小。 1 2 一般是因为在使用搜索的解法的时候，没有判断去掉割边后原点和终点是否连通。
过了这两组应该就是正确的了
[编辑] 问题分析
本题比较麻烦，要用到最小割最大流定理。 首先求出最大流，那么最小割的容量就是最大流的流量。 然后找有没有容量=最小割容量的“桥”（这里的桥就是去掉这条边后，由源点出发无法到达汇点），如果有那么这个桥就是答案。 然后对每条容量不大于最小割的边，去掉后求一次最大流（估计这里我的算法太麻烦了）。如果流量的减少量=这条边的容量，那么这条边一定属于最小割。找出这样所有的边后，如果这些边的容量和=最小割容量，那么符合题目条件的最小割已求出。 剩下的工作就是搜索了。用dfsid，每次增加深度限制，按边的编号大小顺序扩展，搜索是否存在一种方案使得这些边的权值与已求出的必然属于最小割的边的权值之和等于最小割。然后judge一下是否去掉这些边后源点与汇点不连通。如果不连通，则说明已经找到解，可直接输出。 数据规模不算大，一般的BFS已经足可胜任最大流的工作。不过我用的是预流推进，最大数据也不超过0.1s。在熟练的前提下，还是尽量用更好的算法吧^_^。
数据中可能存在两点之间有多条边的情况，可以在求最大流时把这些边并成一条边，然后在求最小割的边集时再拆开。
标程用了一种很不错的方法。因为总共只有1000条边，那么将每个边容量*1001+1作为新的容量（注意这里指每次读入的每个边），那么最大流mod 1001就是最小割去的边数。最大流=值 div 1001。首先这对最大流求肯定没影响，其次，我们知道对以每一条增广路大小取决于最小的那个，这里的+1就派上了用场。 在同样可一减去2条边和减去一条边使其不连通时，减去两条边对应+2>+1所以，求最大流时会选择+1 ，同样，对于那些必须删的边多少个+1其实就等于删了多少条边。 路人甲：我认为如果同时减去两条边的话，对流量的增加这个不还是1么……应该是只对于若该条增光路上已经有一条边在之前被增广过，那么就会有一个0，就不增广1了。
我认为直接枚举满流量的边求删的边是不对的，例如：
1-3:5 1-2-3:5 3-4:5
可能求出最大流为5，可能1-2-3为满流，但此时减去1-2-3，或1-3，都是不对的。必须减去3-4。 用残量网络求出传递闭包可以求出真正必须删的边。
很明显地，这是一个最小割的模型，设每边的权值为原始权值，则最大流的值就是最小割的容量，即最小损失。根据胡兄的论文(07WC)，只要从源点进行一次floodfill就可以得出最小割集。 现在有两个问题：停止的线路数，使开始输入顺序最小 为解决这两个问题，可将每边的权值修改为500000+i+500000*1001*c，这个式子有什么用呢？首先，每边的权值都加上500000，那么最大流(maxflow%(500000*1001))/500000就是停止的线路的数量，取500000的原因是500000> (0+999)*1000/2，即最大情况下0~999的i的和，否则可能由于i的值而使结果偏大。i项的含义就很明显了，为使输入顺序最小。最后一项中的1001则是因为最多有1000条边，所以500000*1001*c > 500000*1000，这三项分别独立，从而得出结果。 程序可以参见： http://dementrock.blog.com/?p=130
个人认为这种加权方式显然无法保证字典序最小，只能保证序号和最小。
我觉得LS说得对，我猜这个应该是C++的第一个代码，对于数据
4 5 1 2 10 2 3 10 2 3 10 3 4 1000 1 2 10
输出了边2 3，实际上应该是边1 5
先求解一次最大流 然后将满流的边全部改成1 然后在求解一次 所得结果即为最少所割遍数 求解方案的话 对第一次最大流网络中慢流且在第二次最大流中满流的边 按照在第一次中通过的增广路径的数目排序 然后取出前最少所割遍数的合法的边--个人想法，未证实
