注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

最大流算法的选择:Dinic还是SAP?  

2010-08-25 18:45:47|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最大流是oi中经常用到的工具之一(尤其是近几年),所以任何一个OIer必然都要背诵一个
代码短、速度快、便于记忆的最大流代码。
曾经某位神牛说”poj3469我试了所有最大流算法,只有dinic过了"
于是,我便毫不犹豫地选择了dinic,不停地实践,直至滚瓜烂熟地背诵下了全部的21行代码。
int level[NMax];
int mkLevel(){
for (int i=(level[0]=0)+1;i<N;i++)level[i]=-1;
static int Q[NMax],bot;
Q[(bot=1)-1]=0;
for (int top=0;top<bot;top++){int x=Q[top];
for (edge *p=E[x];p;p=p->next)if (level[p->e]==-1 && p->f)
level[Q[bot++]=p->e]=level[x]+1;
}
return level[N-1]!=-1;
}
int extend(int a,int b){
int r=0,t;
if (a==N-1)return b;
for (edge *p=E[a];p && r<b;p=p->next)if (p->f && level[p->e]==level[a]+1){
t=p->f;if (t>b-r)t=b-r;t=extend(p->e,t);
r+=t;p->f-=t;OPT(p)->f+=t;
}
if (!r)level[a]=-1;
return r;
}
int Dinic(){int ret=0,t;
while (mkLevel())while ((t=extend(0,1000000000)))ret+=t;
return ret;
}

然而,情况有了变化。

先是在和其他省的选手交流的时候听说了"SAP"这个最大流算法,并且听说它的”常数比dinic好“
我当时将信将疑,稳妥起见,决定不改变自己使用dinic的习惯。
说些题外话。今天,我看《introduction to algorithms》终于看到了最大流那章,并且学习了
Relabel To Front这个算法。带着好奇,我实现了Relabel To Front的代码
(dinic、sap、RelabelToFront最大流代码合集:http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/MaximumFlow.cpp)
用poj3469测试,果不其然地tle了。
但是,看着RelabelToFront的代码,我忽然觉得有点眼熟......

SAP?

是的,sap和RelabelToFront在很多细节上有神似的地方:
都有”距离标号“,都有”当前弧“,都是每次针对一条边操作......
但他们还是本质不同的,一个是ford-fulkerson方法,一个是push-relabel方法。
在更大的好奇的驱使下,我打开了《算法艺术与信息学竞赛》,正式学习了一下SAP。

其实sap非常简单!
它的基础思想还是增广路,不过每次都选”最短“的一条增广路(和dinic其实一样...)
sap的优势就是每次计算距离的时候不是像dinic那样重新bfs计算,而是充分利用以前的距离标号的信息。
就像RelableToFront中一样,sap的距离标号只是一个当前节点到汇的距离的下界,只有在无法根据当前标号增广的时候
才去更改它,使得我们能够找到当前节点的“下家”
代码:
int SAP(){
static int d[NMax],g[NMax+1],Q[NMax];
static edge *c[NMax],*pre[NMax];
int ret=0,x=0,bot;
for (int i=0;i<nn;i++)c[i]=E[i],d[i]=nn,g[i]=0;
d[nn-1]=0;
pre[g[nn]=0]=NULL;
Q[(bot=1)-1]=nn-1;
for (int i=0;i<bot;i++)for (edge *p=E[Q[i]];p;p=p->next)
if (OPT(p)->f && p->e!=nn-1 && d[p->e]==nn)d[Q[bot++]=p->e]=d[Q[i]]+1;
for (int i=0;i<nn;i++)g[d[i]]++;
while (d[0]<nn){
while (c[x] && (!c[x]->f || d[c[x]->e]+1!=d[x]))c[x]=c[x]->next;
if (c[x]){
pre[c[x]->e]=OPT(c[x]);
x=c[x]->e;
if (x==nn-1){
int t=~0u>>1;
for (edge *p=pre[nn-1];p;p=pre[p->e])if (t>OPT(p)->f)t=OPT(p)->f;
for (edge *p=pre[nn-1];p;p=pre[p->e])
p->f+=t,OPT(p)->f-=t;
ret+=t;
x=0;
}
}else{
int od=d[x];
g[d[x]]--;
d[x]=nn;
for (edge *p=c[x]=E[x];p;p=p->next)if (p->f && d[x]>d[p->e]+1)d[x]=d[p->e]+1;
g[d[x]]++;
if (x)x=pre[x]->e;
if (!g[od])break;
}
}
return ret;
}
注意,SAP的实现有无数需要注意的细节,一旦一个细节没有处理,都会导致“灾难”性后果。
这些细节有:一定要bfs求初始标号、一定要保存当前弧、一定要在标号出现“断层”的时候结束、小心地计算当前节点的位置......
但是,战战兢兢地实现代码是值得的!
在poj3469上,
dinic : 3698ms
sap: 2402ms
整整快了一半!
还有一个更迷人的特性:sap的代码是非递归的!
想象这样一个图:由20000个节点组成的从源到汇的链。
dinic会栈溢出,普通的初始标号都是0的sap会tle,只有我上面那个用bfs计算初始标号的代码可以轻松+愉快的秒杀。

现在,终于切入正题了!
在生产生活(包括OI)中,到底应该使用dinic 还是sap算法呢?

先让我们列一下两个算法各自的优势
1.sap比dinic快  这是经过了很多人(包括我)检验的,甚至快的可以不是一星半点儿。
2.sap的非递归实现比dinic好写(我上面的代码就是非递归的)
3.该dinic了。dinic的代码长度短(字节数比sap少1/4)
4.dinic的代码行数比sap少(大约少1/2)
为什么要分别计算代码字节数和行数呢?
这主要是因为我自己的编程习惯:
尽量把目的一致、结构相同的代码挤在一行。
而代码行数少就等价于:需要背诵的内容少、代码的复杂程度低、调试难度小。
而代码字节少就等价于:需要敲得键盘次数少、代码实现时间短。
别不信,再看一眼dinic和sap的代码,你肯定愿意抄写dinic并调试。
这也就让人产生了纠结。为了常数,我们可能要用更多的时间去写代码,并且sap的代码细节众多,
有一堆繁琐的小句子(不像dinic的全部语句就是4个for2个while3个if),调试起来很有风险。

在dinic和sap之间的抉择仿佛就变成了在heapsort和quicksort之间的抉择。
1.良好实现的heapsort在最坏情况下速度比quicksort快的是有本质区别的(随机化?不怕别人challenge 你的代码吗?)
2.heapsort本身就是非递归的
3.quicksort代码量小
4.quicksort代码行数少
结果呢?大家最后都达成了共识:
1.在写一些无关紧要的小题或数据很小时,使用单纯版的quicksort
2.在写一些oj上数据很大的题时,使用加了各种抗恶心(随机化)的quicksort
3.在写一些关乎生死存亡、重大利益的代码时,使用stl中集各种排序之大成于一身的sort函数
4.在写一些关乎生死存亡、重大利益的代码,又禁了stl的时候,用heapsort

于是,我做出了以下选择:
1.同时掌握dinic和sap的代码
2.在小数据或无关痛痒的题目上,使用dinic
3.在noi及以上的正式比赛中,使用sap
4.为了能在关键时刻写出正确的sap,平常也要“勤练兵”,有事没事也写一写。

这个问题似乎也就被解决了,不过是用了一种痛苦的方法:同时掌握两种算法。
其实同时掌握两种算法是有风险的,不过,比起将来可能带来的收益,是非常值得的。

每个人都可以有不同的风格,以上观点仅供参考。

【更新】
两年半之后再看这个文章,发现当时的想法其实很天真。我从没有在考场上写过sap,虽然dinic拍过几遍。与其记忆两个算法,不如把省下来的大脑的内存用来记点别的,例如什么样的题目可以转化为费用流。规律是,越高端的比赛对具体算法的实现越不要求。重要的是,意识到该算什么,具体怎么算则是体力活。
  评论这张
 
阅读(8980)| 评论(31)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017