NOI 2006 — 最大获利(profit)
很经典的一道网络流的题目了.
话说今天很神奇啊,突然就把网络流学会了,还写了两道题都没出错.极力推荐Dinic,又短又好写速度还巨快(不要扯时间复杂度,Dinic的实际速度比预计的快不是一点).原来HopCroft就是简化版的Dinic啊…
这道题需要把每个用户群看做一个结点,每个中转站看做一个结点.然后源连到用户群权值是用户群的获益,用户群连到中转站权值正无穷,中转站连到汇权值中转站花费.
因为最大获益=用户总获益-未选择用户群应得获益-中转站花费=用户总获益-(未选择用户群应得获益+中转站花费)而对于这个网络流模型,它的最小切割的意义就是未选择用户群应得获益+中转站花费.这样,只要求出最小切割,然后用用户总获益减去最小切割就可以了.根据神奇的最小切割最大流定理,求一个最大流,问题解决.
显然我用了Dinic,速度巨爽无比.远远把DFS多路增广甩在了后面(废话…Dinic有分层图思想…).
另:这道题用FPC编译(似乎是老版本),即使除去inline,也会RE掉,不知道为什么.Delphi正常.
还有,我已经无法忍受WP自动将英文标点转成中文,于是找Thity要了些空间.过段时间开通.到时候自己改一下WP的源码.
附程序.
{ NOI 2006; 最大获利; profit - sqybi’s code - 最小切割最大流 - Dinic}//for my winstyprogram profit_sqybi; const fin = ‘profit.in’; fout = ‘profit.out’; nn = 5000; mm = 50000; tt = nn + mm + 2; ee = mm * 3 + nn;
var n, m, i, s, t, r, x, y, z, edgeNum: longint; […]