今天看啥
    热点:

      天发国际娱乐官网:马英九回复说,最近对民粹主义有很多讨论,很多议题需花时间沟通,不能急着立法。

      网络最大流算法—EK算法,最大流ek算法


      前言

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

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

      思想

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

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

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

      实现

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

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

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

      所以我们选用BFS

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

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

      代码

      题目在这儿

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

      #include<iostream>
      #include<cstdio>
      #include<cstring>
      #include<cmath>
      #include<queue>
      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<int>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;
      }

       

      性能分析

       

      通过上图不难看出,这种算法的性能还算是不错,

      不过你可以到这里提交一下就知道这种算法究竟有多快(man)了

       

      可以证明,这种算法的时间复杂度为$O(n*m^2)$

      大体证一下:

      我们最坏情况下每次只增广一条边,则需要增广$m-1$次。

      在BFS的时候,由于反向弧的存在,最坏情况为$n*m$

      总的时间复杂度为$O(n*m^2)$

       

      后记

      EK算法到这里就结束了。

      不过loj那道题怎么才能过掉呢?

      这就要用到我们接下来要讲的其他算法

      www.1click-soft.comtruehttp://www.1click-soft.com/PHPjc/1284238.htmlTechArticle网络最大流算法—EK算法,最大流ek算法 前言 EK算法是求网络最大流的最基础的算法,也是比较好理解的一种算法,利用它可以解决绝大多...

      相关文章

        暂无相关文章
      相关搜索:

      帮客评论

      视觉看点
      百度 360 搜狗