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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

最大流(EK算法和Dinic算法+例题?)  

2016-08-28 21:39:50|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        最大流问题,就是:
        s地往t地运输原料,已知s、t分别是有向图G中的两点,每条有向边都有一定的流量Cij。Cij表示从i点到j点运输不能超过的运输量。图G可以称作一个网络,而s能够运输到t的最大运输量则是该网络的最大流
这里s和t分别称为源点和汇点
======================================
        伤脑筋吧,像这样的问题就叫做最大流问题。这只是别这裸题,应用起来的范围可广了。下面来讲讲做法。不过yhf也是有很多不懂,大概把做法讲了,但为什么这样做,yhf也是不懂……最大流(EK算法和Dinic算法) - 杨鸿飞 - 杨鸿飞的博客
======================================
EK算法(Edmond-Karp,最短路径增广算法):
        先从s到t找一条路径(用bfs找,为了省时间,一般找最近的路径),把这条路径中容量最小的边作为这次的流量,如图:
最大流(EK算法和Dinic算法) - 杨鸿飞 - 杨鸿飞的博客
        为了便于编程,把对应容量减少,就不用记住这条边的流量了。
        然后反复执行这两步,直到找不到增广路为止,这时的最大流就是把每次的流量相加。下一次的增广路为5->4->3。如果容量为0的边,那就走不通。
        然而有反例:
最大流(EK算法和Dinic算法) - 杨鸿飞 - 杨鸿飞的博客
        如果找的增广路是像上图那样,那样最大流就会是4+2+1=7了,那显然是不对的,所以就会有反向边,如图棕色边所示,反向边的容量是原边的流量,可以这么说吧,反向边的存在就可以反悔,走原来走错的路。
        实际上每一条边都有其对应的反向边,不像图中只有一条,图中为了方便才只弄一条的。
        至于反向边为什么能解决,我也不大清楚。
        反向边用链式前向星的写法:“Addedge(i,j,c),Addedge(j,i,0);”这样就存在第i条边的反向边是第i^1条边。
        时间复杂度O(f*n),f为增广次数,最多为n。f较大。
======================================
EK模板:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MLm=200;
const int MLn=200;

int n,m;

struct Tedge { int v,c,nx; }lb[MLm*2+10];

int top[MLn+10],tplb;

void ins(int u,int v,int c) //u到v连一条容量为c的边
{
int tt=top[u]; top[u]=tplb++;

lb[top[u]].v=v; lb[top[u]].c=c; lb[top[u]].nx=tt;
}


bool ff[MLn+10];

int fa[MLn+10],op[MLn+10];

int E_K(int s,int t)
{
int flow=0;

for ( ; ; )
{
int nflow=2100000000;
/*================找增广路===============*/
memset(ff,0,sizeof ff);
memset(fa,-1,sizeof fa);

ff[s]=1; op[0]=s;

bool fff=0;

for (int Head=0,Tail=1; Head<Tail; Head++)
{
int u=op[Head];

for (int kb=top[u]; kb!=-1; kb=lb[kb].nx)
{
int v=lb[kb].v;

if (ff[v] || lb[kb].c==0) continue; //判断允许边

fa[v]=u; ff[v]=1; op[Tail++]=v; //记录父亲,用于增广

nflow=min(nflow,lb[kb].c); //找最小容量

if (v==t) { fff=1; break; }
}

if (fff) break;
}

if (!fff) break;
/*===============增广==============*/
flow+=nflow;

for (int i=t; i!=s; i=fa[i])
{
for (int j=top[fa[i]]; j!=-1; j=lb[j].nx) //枚举边
if (lb[j].v==i && lb[j].c!=0)
{
lb[j].c-=nflow; lb[j+1].c+=nflow; //处理反向边

break;
}
}
}

return flow;
}

int main()
{
while (~scanf("%d%d",&m,&n))
{
tplb=0;

memset(top,-1,sizeof top);

for (int i=0; i<m; i++)
{
int u,v,w;

scanf("%d%d%d",&u,&v,&w);

ins(u,v,w); ins(v,u,0);
}

printf("%d\n",E_K(1,n));
}

return 0;
}

======================================
Dinic算法:
        其实相比上面的EK算法,Dinic算法更高效,更短(yhf还是写的很长……),其实EK慢在哪儿呢,因为EK算法每次只增广一条路径,而Dinic算法可以一次增广整幅图,虽然时间复杂度还是O(f*n),f为增广次数,最多为n。但f一般达不到n,并且会非常小。下面来讲讲做法。
        第一步,BFS求层次图,看起来很高级,就是求每个点的深度。不难。
        第二步,DFS增广。
        
 

 
  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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