一切皆可网络流

图论题,转化到常见模型才是最重要的。


网络流

花了点时间把白书的网络流例题、习题都做了,覆盖的挺全的,主要是建图的技巧吧。 一些简单的题解。


例题:

uva 11248 Frequency Hopping

网络扩容,bzoj上有一道类似的题,就是每次扩展最小割的边,看看够不够。两个优化:

一个是直接在残余网络内增广,一个是不用求最大流,当增广到C就不用增广了。忘记将belong置0,wa了一次。

la 2957 Bring Them There

这个题也是一个网络流处理天数的模型吧,将每个点拆成t个点,然后 ai->bi+1 这样连边。实际上是不用处理同时有 ai->bi+1 和 bi->ai+1 因为实际情况下与去掉冲突的那部分等价。这个题,有两种实现方式二分或者迭代。写的迭代。所有的输出方案的题都很坑很坑。

la 2531 The K-league

利用网络流来判断有限制的方案是否可行,书上讲的比较清楚。注意如果一个队的total 小于 max{w[i]}。它也是不可行的,如果不管它就判断,就会在网络中连一条负边使答案算错。

uva 10779 Collectors Problem

一道比较神奇的构图题。书上讲的很清楚。每一个流都可以代表一个合法交换。

uva 11613 Acme Corporation

最小费用流,把每个点拆成两个点i和i',然后s对每个月i连边,容量为产量,费用为单位生产成本。然后i向i',(i+1)',(i+2)'..(i+Ei)',容量inf,费用I*月份,然后从每个i’向T连边,费用为-售价,容量为最大销售量,然后求最小费用流即可。(拆点是为了隔离每个月之间的关系。) 注意uva上样例是错的,书上是对的。注意ans为longlong。


习题:

uva 10806 Dijkstra, Dijkstra.

费用流,S向1连容量2,费用0的边,然后按照图连边,容量都为1,费用为距离,若最大流==2 ,则可以实现,答案为cost。

la 3268 Jamie’s Contact Group

二分,最大流,S向每个人连边容量1,每个人向各个组连边,容量1,然后二分答案ans,每个组向T连边容量ans,看最大流是否等于n。(输入和二分时状态还原需要注意。)

uva 11167 Monkeys in the Emei Mountain

由于猴子最多有100只,但是时间范围确实5000,所以可以离散化时间,将时间分段,记录每一段的开始,和每个开始对应的哪一段,由S向每个猴子连边容量为v,然后每个猴子向 a->b这些段时间连边,容量为时间段长度,每段时间向T连边,容量为m*时间段长度,最后还要输出方案,输出方案时,就相当于把一个时间段填满,记录上次填到哪了,如果超过了,就分成两段填,然后就解决了。(刚开始数组开小了,调了一个小时。。)

uva 11082 Matrix Decompressing

先把前缀和序列差分成每行和每列的和,又因为每个元素都是大于等于1小于等于20的,可以当做每个元素已经是1了,然后行列和减去对应的1的个数,然后s向每行连边,每列向t连边,容量就是行的和或列的和,然后在行列之间连n*m条边,容量是19(因为假设每个元素都已经是1了),然后求一遍最大流,中间n*m条边上的流量+1就是矩阵该点的数值。

la 3645 Objective:Berlin

时序模型,将航线当作点,拆成两个一个入点一个出点,然后枚举每个点中转,连边就好了。字符串的城市名用map<string,int>就好了。

la 4597 Inspection [推荐]

边可以重复选择的最小路径覆盖,转化为有容量下界的最小流。具体做法参考链接 输出方案又是坑。

写这道题的时候顺手写了个datamaker对拍用。链接

la 3972 March of the Penguins

节点容量,最大流。枚举每个点为t,比较简单吧。

la 3487 Duopoly

//未完待续,后几道题让我好好想一想

la 2197 Paint the Roads

la 2796 Concert Hall Schedule

la 5095 Transportation

la 5131 Chips Challenge



附录A 网络流

如果有时间的话


uva 10280 shougi tournament

uva 11380 Down Went the Titanic

uva 11544 Recruiter’s Problem

uva 11594 All Pairs Maximum Flow

uva 11647 Judgment Day


真是一项大工程啊。感谢lrj的翻译。

总感觉网络流很神奇,图建好了,它自动就平衡了一些东西,出答案了。
以上。 官方题解