USACO/telecow

来自NOCOW

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .4中的OI题目TeleCowmunication的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] 问题分析

算法和4.4的pollutant control(求最小边割集)类似，但这道题是求最小点割集。

我们可以把每个点i拆成两个点i1,i2，这两个点之间建立一条边权为1的有向弧。对于原图中边(i,j)，建立(i2,j1)和(j2,i1)两条边权为∞的有向弧。这样就把求最小点割转化成了求最小边割。

根据最大流最小割定理：源S到汇T的网络最大流等于S与T间最小边割集的容量和。只需对新图求网络最大流，记为netflow，在这里我用了Dinic。这样就完成了第一问，结果为netflow。

第二问，求最小边割集的办法可参考07年胡伯涛的论文，用一次floodfill即可

最后，因为要输出字典序最小，边权可修改为6000+i，其中i为编号，最后maxflow的结果再除以6000即可

————————————————————————————————————————————————————————————————————————

其实不拆点也能做，求最大流的时候不断用Dijkstra求源点到汇点的最短路，总流量加一，删去路径上的点，直到找不到路径为止。先求原图的最大流value，然后枚举每一个点，如果删除它后最大流减少1则将其放入数组。value就是答案的个数，dfs一下就能得到答案。(详见PASCAL程序)

[编辑] 我的一点想法

我觉得改边权为6000+i不能保证字典序最小，只能保证选出来的点的编号和最小。我想的方法和Chapter 4的那题差不多，顺序枚举删除每一条拆点连的边，然后看是否流量的变化只是少了1。程序贴在C++的范例程序里了。

边权为6000+i确实是错的 20 7 1 2 1 4 1 5 4 3 4 20 5 20 3 2 20 2 只能保证和最小不能保证字典序最小，这组数据应为3,20；若改边权就成了4,5了

[编辑] 保证正确性的改进

//by huyuanming11 其实我们可以把边权设为一个很大的数+2^(编号-1),求最大流,然后把结果模上这个很大的数,剩下来的就是每条边取/不取组成的二进制编码.这样的正确性是可以证明的,但是问题是这样加减等运算的复杂度就会到达O(n).我们可以自己实现一个高精度的模块,支持很长的二进制整数的加减,比较等.同时,这样也带来的很大的代码量.毕竟比赛的时候得分才是硬道理,这种方法和上面正确性欠佳的方法各有优势.当然,如果会完美算法就更好了,毕竟这只是骗分用的......

这种方法能跑过 20 7 1 2 1 4 1 5 4 3 4 20 5 20 3 2 20 2 这组数据吗？

[编辑] 关于*6000+i必然错误的说明

不仅不是保证字典序最小，而且有可能满足字典序之和最小的有多种方案在此提出一种新的算法，即从小到大枚举边，跑最大流，如果这条边可行，就将它删掉，继续枚举这样跑出的边就一定是字典序最小了。（类似于贪心。。算法的前提是最小割的边数已确定）

[编辑] 参考代码

C

C++

Pascal