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

Who I am.

庸人只顾自我陶醉 Aftc、

 
 
 

日志

 
 

Network Flow  

2015-04-10 21:26:33|  分类: Informatics |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Studying Notes:

 

(零)

我是怀着十分激动的心情打这篇笔记的,也许这下意味着我真正脱离了普及组,成为水平更高一点的……蒟蒻了吧。

 

(一)

网络流是什么

 

它是一类关于有向图上流量的问题(不是手机流量= =),想必很多人都无意中在初中的数学竞赛中遇到过了,没错就是这么坑爹:

Network Flow - Dirak - OIers Dream

——感谢童施提供的真迹 OTZ。

 

就像上图所说,每条边有一个最大流量(即容量),有一源点S和一汇点T,网络流问题就是研究这样子的网络的性质,常见的有最大流问题,即求源汇最大流量。

 

由于水平/时间/篇幅有限,这篇东西只考虑最大流的一些解决方法,更多的东西以后补上。

 

残量网络

 

假设在一个流量图里,已经选了若干条边,在它们上面添加了流量:

Network Flow - Dirak - OIers Dream

每条边上,斜杠前的数是已有流量,斜杠后是边的容量。

 

我们发现以这个图现在的情况已经不能再加流量了,但是这并非是可以达到的最大流量。这说明了如果只是随心所欲地加一些流量的话,得到的答案也许不是最优解。

 

所以在情况不是最优时,我们应该加一个“回溯”的机制,也就是要能够“反悔”。

 

残量网络就因此被研究出来了,经研究发现,只要在每条流过的边上添一条“反向弧”就可以实现回溯:

Network Flow - Dirak - OIers Dream

上图就是第一张图的残量网络,红色的边是反向弧,黑色的边上面的数是剩余的容量,灰色的边已经被填满,剩余容量为0,因此不在残量网络中。

 

为什么呢?感性地想一想:如果有了反向弧,原来从u流到v,现在可以从流过去的地方再流回来,即从v流到u 。如果一条边和它的反向弧都被流过,可以看做流量是“抵消了”,于是可以就做到“退流”。

 

最优答案如下,请自行手推理解:

Network Flow - Dirak - OIers Dream 

 

增广路(Augment Path)

 

如果有一条从源点到汇点的路径并且路径上的边都没有到达容量上限,也就是说没有“堵死”,说明可以使得这条路可以再通过一些流量,使得将它“堵死”,然后总流量就会增大,我们称这样的路径为增广路。

 

达到最大流当且仅当网络中没有增广路(很显然的呀,反正我不会证明),这就是增广路定理。

 

其实最大流的思想有两种,一种是不断寻找增广路并且堵死它,另一种就是预(wo)流(cai)推(bu)进(hui)算法。最优化的预流推进据说能到达O(n^2√m)这样令人发指的复杂度,但是代码长度同样令人发指(和红黑树很像),由于一般增广路算法已经够用了,所以只介绍基于增广路的算法。

 

 

(二)

SAP算法也就是Edmonds-Karp算法

 

利用增广路定理,很显然的想法是暴力找增广路,然后进行拓展。怎么找呢?DFS吗?很容易会被卡。所以我们还是用BFS吧。

 

算法框架:

1)源点S入队

2)从队列中拿出队首U,将与U有边的点V全都加入队列(注意这里的边是残量网络中的边),并且用pre[V]记录每个点V是从那条边走过来的。

3)如果没有找到汇点T,重复2),否则从pre[T]一路往回修改增广路上的流量,并且修改反向弧。队列清空然后回到1)。

 

可以证明最多经过O(n+m)次增广可以找完所有增广路,每次Bfs复杂度O(m),所以总复杂度是O(n*m^2)的

 

完整代码: http://dream-for-me.lofter.com/post/1d071ee2_68d6163 

(文章太长了网易不让发= =,下面只放核心代码,EK没什么用就放代码库)

 

(三)

可以想象,这样子愣头青的暴搜效率肯定不怎么样,怎么优化呢?

 

Dinic算法

 

发现每次用Bfs找增广路,找到的肯定是最短增广路。所以才叫做SAP(Shortest Augment Path)算法嘛。

 

我们为什么不可以先预处理出Bfs呢?可以先Bfs一次,标记处每个点到源点的距离stage[i],称为它的层次,于是建立了一个层次图。然后在这个层次图上Dfs,Dfs时可以从U到V的条件是stage[U]+1==stage[V],可以保证每次找到T的时候都是经过了最短增广路的,和SAP效果一样,显然是正确的。

 

再分析复杂度,O(n+m)次增广,每次用Dfs是O(n)的,所以总复杂度O(m*n^2)。

 

优化:

1)同一个层次图中,记录每一个点当前考虑到哪一条弧,之前考虑过的弧就不要再考虑了。即当前弧优化。

2)当前在找的路径上可通过流量为0时,就不可能是增广路了,立刻掉头。

 

Code(C++):

inline int Bfs(){

queue<int> Q;

memset(stage, 0, sizeof(stage));

Q.push(S); stage[S]=1;

while(!Q.empty())

{

int u=Q.front(); Q.pop();

for(int i=head[u]; i>=0; i=edge[i].next)

{

int v=edge[i].to;

if(!stage[v] && edge[i].cap>edge[i].flow)

{

stage[v]=stage[u]+1;

Q.push(v);

}

}

}

return stage[T];

}

 

int Dfs(int u, int inf){

if(u==|| !inf) return inf;

int flow=0, ret;

for(int& i=cur[u]; i>=0; i=edge[i].next)

{

int v=edge[i].to;

if(stage[v]==stage[u]+1 && (ret=Dfs(v, min(inf, edge[i].cap-edge[i].flow)))>0)

{

edge[i].flow+=ret;

edge[i^1].flow-=ret;

flow+=ret;

inf-=ret;

if(!inf) break;

}

}

return flow;

}

 

inline void Dinic(){

while(Bfs()){

for(int i=1; i<=n; i++)

cur[i]=head[i];

FLOW+=Dfs(S, 1e9);

}

}

 

 

(四)

ISAP算法

 

这是SAP算法的进化版。

 

算法基于这一事实:在增广过程中每个点在残量网络中到汇点的距离不会变小,和Dinic类似,倒过来以在残量网络中到汇点的距离为层次,进行Dfs。

 

而且ISAP不需要在找完当前层次图中的增广路后重建层次图,它是在寻找路径和修改流量的同时进行对层次图的维护,该操作称为Retreat:如果当前点U找不到任何点V满足stage[U]==stage[V]+1,说明要对U的层次进行修改,修改为比所有V中最小stage[V]的多一,即min{stage[V]}+1。如果已经不能到达汇点T,层次直接改为n+1即可。

 

还有对于ISAP效率不满的人加了丧病的gap优化:记录每个层次中有几个点,如果某次Retreat后导致某个层次中没有点了,说明S、T不连通,不可能有增广路了,直接退出算法。

 

这样一来实现了SAP的逆袭,成就了平均速度奇快的ISAP。

 

Code(C++):

void Bfs(){

queue<int> Q;

for(int i=1; i<=n; i++)

stage[i]=n+1;             /* 要考虑无法达到的点 */

stage[T]=1;

Q.push(T);

while(!Q.empty()){

int u=Q.front(); Q.pop();

for(int i=head_[u]; i>=0; i=edge_[i].next){

int v=edge_[i].to;

if(stage[v]==n+1){

Q.push(v);

stage[v]=stage[u]+1;

}

}

}

}


inline int Augment(){

int inf=1e9;

for(int u=T; u!=S; u=edge[pre[u]].from)

inf=min(inf, edge[pre[u]].cap-edge[pre[u]].flow); /* 找增广路上流量 */

for(int u=T; u!=S; u=edge[pre[u]].from)

{

edge[pre[u]].flow+=inf;

edge[pre[u]^1].flow-=inf;

} /* 更新残量网络 */ 

return inf;

}


inline void ISAP(int &Flow){

Bfs();

for(int i=1; i<=n; i++){

num[stage[i]]++;

cur[i]=head[i];

}

int u=S;

Flow=0;

while(stage[S]<=n){

if(u==T){

Flow+=Augment();

u=S;

}

bool flag=0;

for(int &i=cur[u]; i>=0; i=edge[i].next){ /* Advance  当前弧优化 */

int v=edge[i].to;

if(stage[v]+1==stage[u] && edge[i].cap>edge[i].flow){

flag=1;

pre[v]=i;

u=v;

break;

}

}

if(!flag){                    /* Retreat  边增广边修改层次 */

int tmp=n;

for(int i=head[u]; i>=0; i=edge[i].next){

int v=edge[i].to;

if(edge[i].cap>edge[i].flow)

tmp=min(tmp, stage[v]);

}

if(--num[stage[u]]==0) break; /* gap  优化 */ 

num[stage[u]=tmp+1]++;

cur[u]=head[u];

if(u!=S) u=edge[pre[u]].from; /* Retreat可能使上一个节点层次改变,后退 */ 

}

}

}

 

 

 

Exercise:

1).  http://poj.org/problem?id=1273

模板,木有什么好说的,可以用三种算法分别AC

 

2).  http://poj.org/problem?id=3281

点有容量,用拆点的思想

 

3).  http://poj.org/problem?id=2455

详解:http://dream-for-me.blog.163.com/blog/static/245077059201531085836892/

 

4).  http://poj.org/problem?id=2391

详解:http://dream-for-me.blog.163.com/blog/static/2450770592015310965458/

  评论这张
 
阅读(22)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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