NOI 2006 — 最大获利(profit)

Posted on 四月 7th, 2008.

很经典的一道网络流的题目了.
话说今天很神奇啊,突然就把网络流学会了,还写了两道题都没出错.极力推荐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;    […]

NOI 2006 — 生日快乐(happybirthday)

Posted on 四月 5th, 2008.

这道困扰了我许久的题目,终于被我过掉了…
话说当时觉得这道题太难写,于是一直没敢写…然后呢,现在Splay写熟悉了,正好FNOI做这道题,于是咬咬牙开始写.这个东西的调试实在是太恶心人了,不过还好,在用尽方法把file of integer转成text之后,终于能调试了…
写错了两个地方,一个是如果刚插入一个人有x个果冻,而要吃掉的那包也有x个果冻,这是我会把刚插入的那个人的果冻吃掉…加了个小判断搞掉.第二个是,friendID变量用重了…把一些改成了friendID_,过掉~
程序写的不是太恶心.用object写的,然后速度有些慢.于是删了object,加上inline,速度快了些.偶然删去了inline,速度竟然更快!想起了HopCroft那个问题…现在还不知道怎么回事,等着周源来问他…
{
生日快乐; happybirthday; NOI 2006
- sqybi’s code
- Splay
}
//for my winsty
program happybirthday_sqybi;
uses
happybirthday_p;

const
nn = 500000;

type
link = ^obj1;
obj1 = record
v: longint;
[…]