SGU 185 — Two Shortest

Posted on 四月 8th, 2008.

经典的最短路+网络流的题目.
第一行n,m,表示n个点m条边.接下来m行,每行描述一条无向边.x y z表示x,y之间一条无向边,长度为z.要求求出两条没有公共边的最短路.
首先一个SPFA,目的是保留dist数组.然后从最后一个结点开始BFS.对于BFS到某个结点x,如果结点y能够满足dist[y]+table[x, y]=dist[x],则将这条边作为y->x的有向边加入新图中,并将y加入BFS队列(如果y没有被加入过).这样,新图中的边便都是能够构成最短路的边了.接下来对于新图,每条边的容量都看作1,源是1,汇是n,做最大流.得出的最大流就是最短路条数.如果条数少于2,输出无解.如果大于等于2,那么这时我们会获得刚刚计算最大流时的flow数组.从源开始进行DFS,每次只走flow=1的结点,直到走到汇为止,把这条路径上所有flow都变成0.然后再走一次.得到的两条路径输出即可.
然后呢,我的网络流写的是Dinic.于是,我的SPFA+Dinic就华丽的MLE掉了.
谁知道怎么优化内存…开链表不管用,链表会让内存更大.
Update:经过一晚上恶心死人的优化,终于AC了这道题.因为Delphi没有integer类型(Delphi的integer=fpc的longint…而我找不到相当于fpc的integer的类型),于是优化难了很多.最后用上了word,shortint和子界类型,终于AC掉.题目限制1MB内存,我用了1009KB,好险…另外据Wind牛说,可以用最小费用流解.只要加一个源,流2的流量就行.似乎Wind牛还有一个两遍SPFA的算法,未证明正确性.
{ SGU 185; Two shortest - sqybi’s code - 单源最短路 + 最大流 - SPFA + Dinic}//for my winstyprogram sgu185_sqybi;  const    nn = 400;    mm = nn * nn div 2;    unable = nn * 10000 + 1;
  var    n, m, i, qe, qs, r, edgeNum, x, y, z: longint;    t: array[1..nn, […]

Read Full Post | Make a Comment ( 6 so far )

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;    […]

Read Full Post | Make a Comment ( 5 so far )

Liked it here?
Why not try sites on the blogroll...