网络最大流算法—EK算法-白红宇

网络最大流算法—EK算法

阅读量：6992 次

发布时间：2019-06-27

本文共 2366 字，大约阅读时间需要 7 分钟。

前言

EK算法是求网络最大流的最基础的算法，也是比较好理解的一种算法，利用它可以解决绝大多数最大流问题。

但是受到时间复杂度的限制，这种算法常常有TLE的风险

思想

还记得我们在介绍最大流的时候提到的求解思路么？

对一张网络流图，每次找出它的最小的残量（能增广的量），对其进行增广。

没错，EK算法就是利用这种思想来解决问题的

实现

EK算法在实现时，需要对整张图遍历一边。

那我们如何进行遍历呢？BFS还是DFS？

因为DFS的搜索顺序的原因，所以某些毒瘤出题人会构造数据卡你，具体怎么卡应该比较简单，不过为了防止大家成为这种人我就不说啦(#^.^#)

所以我们选用BFS

在对图进行遍历的时候，记录下能进行增广的最大值，同时记录下这个最大值经过了哪些边。

我们遍历完之后对这条增广路上的边进行增广就好啦

代码

代码里面我对一些重点的地方加了一些注释，如果我没写明白的话欢迎在下方评论:blush:

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN=2*1e6+10;const int INF=1e8+10;inline char nc(){    static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){    char c=nc();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=nc();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}    return x*f;}struct node{    int u,v,flow,nxt;}edge[MAXN];int head[MAXN];int num=0;//注意这里num必须从0开始 inline void add_edge(int x,int y,int z){    edge[num].u=x;    edge[num].v=y;    edge[num].flow=z;    edge[num].nxt=head[x];    head[x]=num++;}inline void AddEdge(int x,int y,int z){    add_edge(x,y,z);    add_edge(y,x,0);//注意这里别忘了加反向边 }int N,M,S,T;int path[MAXN];//经过的路径int A[MAXN];//S到该节点的最小流量inline int EK(){    int ans=0;//最大流     while(true)//不停的找增广路    {        memset(A,0,sizeof(A));         queue
          
           q;//懒得手写队列了。。。 q.push(S); A[S]=INF; while(q.size()!=0) { int p=q.front();q.pop(); for(int i=head[p];i!=-1;i=edge[i].nxt) { if(!A[edge[i].v]&&edge[i].flow) { path[ edge[i].v ]=i;//记录下经过的路径，方便后期增广 A[edge[i].v]=min(A[p],edge[i].flow);//记录下最小流量 q.push(edge[i].v); } } if(A[T]) break;//一个小优化 } if(!A[T]) break;//没有可以增广的路径，直接退出 for(int i=T;i!=S;i=edge[path[i]].u)//倒着回去增广 { edge[path[i]].flow-=A[T]; edge[path[i]^1].flow+=A[T];//利用异或运算符寻找反向边，0^1=1 1^1=0 } ans+=A[T]; } return ans;}int main(){ #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); N=read(),M=read(),S=read(),T=read(); for(int i=1;i<=M;i++) { int x=read(),y=read(),z=read(); AddEdge(x,y,z); } printf("%d", EK() ); return 0;}