网络流 Edmons-Karp 算法讲解

87 阅读 0 评论 58 点赞

我是靠谱客的博主还单身大炮，最近开发中收集的这篇文章主要介绍网络流 Edmons-Karp 算法讲解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

网络流EK算法
数据结构：队列
主要操作:广搜 记录路径 更新
能解决的问题：最大流（最小割）
复杂度：O(MV)v指最大容量，M指边数。
新名词：
    1.增广路：从源点source到tink的一条简单路，如果路上的每条边（u，v）的可改进量均大于0，则称这条路为一条增广路。
    增广路定理：网络达到最大流量当且仅当不存在增广路。
    增广路算法：从一个可行流开始不断的寻找可增广路，然后沿着它增广，直到它不存在。
    2.反向弧：如果有一条弧(u,v),那么再进行网络流算法时，要对它建立反向弧(v,u),反向弧的容量为0，与正向弧相反，正向弧减少容量时，反向弧增加容量。建立反向弧能更多的增广，使网络流算法正确。（无法给出证明）
    3.可行弧：在EK算法中指可从u到v增加流量（也就是容量不为0）。
    4.可行路：从源点source到tink的有可行弧构成的路径叫做可行路。    

具体操作：
    1.建立网络（正向弧+反向弧）
    2.从源点出发，广搜一条最短可行路（即最先到达汇点tink的那条路），每次到达一个点用pre数组记录是由那条边过来的（为后面减小流量做准备）
    3.到达汇点tink时，按照pre数组记录的，从可行路中找一条容量最小的进行容量减少。即找到了一条割边。
    4.重复操作2.3，直到无法到达汇点，算法结束，即找到了最大流，算法结束。

推荐水题：USACO 4.2.1 纯网络流算法，可用来试EK的正确性，但EK只能拿50分！

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 #define INF 1000000  
  8 
  9 struct    Edge
 10 {
 11     int x,y,flow,next,op;//flow表示当前边的容量  op表示正向弧所对应的反向弧在边表中的位置
 12 };
 13 
 14 Edge map[200];
 15 int que[20000];
 16 bool b[500];//用b数组记录是否入队，可以防止重复入队，因为有反向弧和环！！
 17 int source,tink,n,m,tot,ans,head,tail;
 18 int first[500];
 19 int pre[500];
 20 
 21 int fmin(int x ,int y)
 22 {
 23     if (x<y)    return x;
 24     else return y;
 25 }
 26 
 27 void Build(int x ,int y ,int c)
 28 {
 29     tot++;//正向弧
 30     map[tot].x=x;
 31     map[tot].y=y;
 32     map[tot].flow=c;
 33     map[tot].next=first[x];
 34     first[x]=tot;
 35     map[tot].op=tot+1;
 36     tot++;//反向弧
 37     map[tot].x=y;
 38     map[tot].y=x;
 39     map[tot].flow=0;//反向弧容量为0
 40     map[tot].next=first[x];
 41     first[x]=tot;
 42     map[tot].op=tot-1;
 43 }
 44 
 45 void init()
 46 {
 47     memset(first,0,sizeof(first));
 48     tot=0;     ans=0;
 49     scanf("%d%d",&m,&n);
 50     for (int i=1; i<=m; i++)
 51     {
 52         int x,y,c;
 53         scanf("%d%d%d",&x,&y,&c);
 54         Build(x,y,c);                
 55     }
 56     source=n+1;     tink=n+2;//手动建立源点和汇点，看题目要求！
 57     Build(source,1,INF);
 58     Build(n,tink,INF);
 59 }
 60 
 61 bool Bfs()
 62 {
 63     memset(b,false,sizeof(b));
 64     head=1;    tail=1;     que[1]=source;    b[source]=true;    pre[source]=-1;//没有可以到源点的路
 65     while (head<=tail)
 66     {
 67         int x=que[head];
 68         int t=first[x];        
 69         while (t>0)
 70         {
 71             int y=map[t].y;            
 72             if (map[t].flow>0    &&    b[y]==false)//找到一条可行弧
 73             {                
 74                 tail++;
 75                 que[tail]=y;
 76                 b[y]=true;
 77                 pre[y]=t;//路径记录
 78                 if (y==tink)    return true;//到达汇点，退出广搜
 79             }
 80             t=map[t].next;
 81         }
 82         head++;
 83         b[x]=false;
 84     }    
 85     return false;
 86 }
 87 
 88 void updata()
 89 {    
 90     int Min=INF;
 91     for (int p=pre[tink];p!=-1;p=pre[map[p].x])    
 92     {
 93         Min=fmin(Min , map[p].flow);//找可行路中的最小容量
 94     }
 95     for (int p=pre[tink];p!=-1;p=pre[map[p].x])//更新容量过程    
 96     {
 97         map[p].flow-=Min;
 98         map[map[p].op].flow+=Min;//反向弧增加容量
 99     }
100     ans+=Min;    
101 }
102 
103 void EK()
104 {
105     
106     while (Bfs()==true)
107     {
108         updata();    
109     }
110     printf("%dn",ans);    
111 }
112 
113 int main()
114 {
115     freopen("ditch.in","r",stdin);
116     freopen("ditch.out","w",stdout);
117     init();
118     EK();    
119     return 0;    
120     fclose(stdin); fclose(stdout);
121 }