网络最大流算法—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那道题怎么才能过掉呢?

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CreateAMind

神经网络图灵机(Neural Turing Machines, NTM)论文完整翻译

19040
来自专栏日常分享

从实例中了解动态规划的基本思想

动态规划,是一种解决棘手问题的方法,它将问题分成小问题,并从解决小问题作为起点,从而解决最终问题的一种方法。

9410
来自专栏生信宝典

R语言可视化学习笔记之ggridges包

作者:严涛 浙江大学作物遗传育种在读研究生(生物信息学方向)伪码农,R语言爱好者,爱开源。

20640
来自专栏人人都是极客

【免费教学】Tensorflow Lite极简入门

边缘计算时代离我们越来越近,当前嵌入式设备的智能框架还是 TensorFlow Lite比较成熟,这里我准备用一系列免费课程和大家一起讨论下 TensorFlo...

25920
来自专栏marsggbo

LaTeX IEEE模板

网上有很多LaTeX软件,在线编辑器推荐Overleaf。但是我个人还是更喜欢离线写东西,所以尝试过各种编辑器,例如VSCode等等,这些编辑器都需要自己搭环境...

37720
来自专栏人工智能LeadAI

机器学习实战 | 第一章:sklearn常用工具介绍

写在前面: 花了大力气学了很多的理论,也用Python实现了其中大部分的算法.接下来开始就进入实战阶段了. 实战阶段有三个重点: 1.选择合适的机器学习框...

306100
来自专栏云时之间

NLP系列学习:常用的语言平滑模型

不过在MIT的NLP课程ppt中总结说有三种模式:Discounting, Interpolationg, Back-off

41290
来自专栏算法修养

文本分类学习 (十)构造机器学习Libsvm 的C# wrapper(调用c/c++动态链接库)

前言: 对于SVM的了解,看前辈写的博客加上读论文对于SVM的皮毛知识总算有点了解,比如线性分类器,和求凸二次规划中用到的高等数学知识。然而SVM最核心的地方应...

11220
来自专栏新智元

深度学习挑战冯·诺依曼结构

【新智元导读】想挑战冯·诺依曼,就必须从三个要素入手:基本操作,例如加减乘除;逻辑流程控制,例如if-else-then,for,while;设存储器,内存和硬...

411110
来自专栏人工智能头条

如何用微信监管你的TF训练?

17630

扫码关注云+社区

领取腾讯云代金券