网络最大流入门

前言

网络最大流是网络流中最基础也是最重要的部分,后边的许多模型也都是由最大流问题引申而来的

最大流

在研究这个问题之前,让我们先来学习一下前置知识

可行流

设f(u,v)表示边(u,v)的当前容量上限

设c(u,v)表示边(u,v)的最大容量上限

如果网络流图中的流量满足

  • 源点S:流出量=流量总量
  • 汇点T:流入量=流量总量
  • 任意边(u,v):0<=f(u,v)<=c(u,v)

则称该流为一个可行流

增广

增广:即增加一条路径上的流量

增加一条路径的流量,即减少这条路径的当前流量上限,即f(u,v)的值

增广是我们求解最大流的基础

最大流

定义:在所有可行流中流量最大的流

那么我们如何求解这个东西呢?

很显然的一种思路就是找到整个网络中的容量上限最小的边

增广(就是加流量)这条路径,不断的重复

暂且不说这么做时间复杂度如何

我们先考虑一下它的正确性。

这么做貌似很有道理,

但是!

以上图为例,如只是无脑增广的话,很可能对SABT这条边进行增广,而增广完这条边后,就再也没有可以增广的路径了,求出的最大流为$3$,下图为增广后的网络流图

很显然,这么做是错的,因为我们可以分别增广SAT,SBT这两条路径,得到的流量为6

那怎么解决这个问题呢?

我们需要引入一个非常重要的概念——反向边

例如,对于SA这条容量为3的边,我们可以认为存在一条容量为0的边AS与之对应,对于SA进行增广,即减小它的容量上限,相当于增大AS的容量上限

也就是说,我们允许从SA流出的流量倒流回去,给它一个悔改的机会

这样,对于上图而言,我们可以借助反向边来更改自己的错误操作,建立反向边后的图如下图所示

这样我们便又有了一条新的增广路SBAT,对这条路径进行增广后我们便可以得到网络最大流为5

考虑一下,为什么这样是对的?

原因很简单,造成我们刚开始做出错误决策的边为AB,最大流本不应经过这里,但是我们却无脑的经过了这里

因为反向边BA的存在,我们又把从A流向B的流量给退了回去。这就相当于没有经过AB这条边

(本节以下内容读者可以直接略过,属于本蒟蒻瞎扯,可能把读者带到沟里面,目前已有一人受害) 反向弧到这里本就应该结束了,但是本蒟蒻在学习的过程中一直有个问题不明白 为什么加反向弧是对的? 如果不考虑反向弧,我们选择的路径为$SAT$,$SBT$,但是加了反向弧之后我们的路径貌似不是这么选的啊。。 尤其是$AT$这条边的流量,本应该是从$SA$流过来,但实际是从$SB$流过来。 这样为什么是对的呢? 这个问题我思考了很长时间,最终得出了一个很不靠谱的结论 因为经过$AB$这条边的流量为$SA,AB,BT$的最小值,然后xjb分情况讨论一下,%……&*()()*&……%¥)(大概要分个一二十种情况吧,然后发现都是对的,其实就是各边之间的流量等效替代问题。。。) 看到这儿的同学,恭喜你们被带到坑里啦O(∩_∩)O哈哈~

实现

我目前见过的最大流算法有以下几种

  1. EK(最简单,比较慢)
  2. Dinic(最常见,性能良好)
  3. ISAP/SAP(也比较常见,性能很好)
  4. 最高标号预流推进(HLPP) (暂时还没学。。)
  5. 前置重贴标签(什么鬼。。。)
  6. 推送重贴标签(WTF......)

对于这些算法,博主给大家的建议是:

  • 理解第一种方法,并用代码实现一次
  • 熟练掌握第二种算法,深刻的理解其内涵,并能做到超级熟练的运用(起码5min之内要敲出来&&没有错误)
  • 理解第三种算法,并至少运用一次。(因为第三种算法跑的比较快,所以可以用来抢排行榜$rank1$)
  • 第四五六中算法建议大家理解其内涵,代码实现就无所谓了,因为基本用不到,不过学会了可以用来装13:joy:

另外,在书上看到过据说可以使用动态树优化最大流算法,但是把百度翻遍了也没找到代码。。。

如果您会的话欢迎教一下本蒟蒻,感激不尽

由于想讲的详细一些,所以想了一下把每个算法分开讲吧,我会尽快更新哒:grinning:

(最近这几天可能不太好办了,因为博主在外面学(bei)习(nue),只有晚上才能更博客)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

一篇文章学会miRNA-seq分析

第一讲:文献选择与解读 前阵子逛BioStar论坛的时候看到了一个关于miRNA分析的问题,提问者从NCBI的SRA中下载文献提供的原始数据,然后处理的时候出现...

2.2K7
来自专栏机器人网

自平衡机器人的控制系统设计

引 言 移动式机器人在各行各业具有广泛的应用,而轮式移动机器人由于具有结构简单、可控性强、成本低等优点,成为移动式机器人研究的一个主要方向。自平衡机器人采用水...

2965
来自专栏PPV课数据科学社区

工具 | 一张图,教你用25种可视化工具如何完成

散点图真是一个比较神奇的图形,正如它的名字一样,一堆纷乱如麻的圆点,看似无迹可寻却能显示出数据难以显示的内在逻辑关系。很多人称它“万表之王”,它在数据分析师手...

4238
来自专栏流柯技术学院

性能测试学习之三—— PV->TPS转换模型&TPS波动模型

TPS = ( (80%*总PV)/(24*60*60*(T/24)))/服务器数量

2492
来自专栏Crossin的编程教室

OpenCV-Python,计算机视觉开发利器

人工智能,一个已经被谈论了几十年的概念(最早是图灵在1950年提出)。如今这几年,相关技术的发展速度是越来越快。高大上如无人驾驶、智能安防、AI辅助诊断,接地气...

2212

在统一的分析平台上构建复杂的数据管道

在Quora上,大数据从业者经常会提出以下重复的问题:什么是数据工程(Data Engineering)? 如何成为一名数据科学家(Data Scientist...

2708
来自专栏人工智能头条

聚类分析算法在Netflix服务器异常自动侦测中的应用

1652
来自专栏安恒信息

解析阻止机器学习的十种网络攻击

即使是瑟曦.兰尼斯特的阴谋诡计或者乔拉.莫尔蒙爵士父亲般的保护(译注:两者都是HBO剧集《权力的游戏》中的人物)也无法阻止攻击者攻破HBO的网络并窃取了1.5T...

3057
来自专栏IT大咖说

当Elasticsearch遇见智能客服机器人

摘要 本次分享主要会介绍一下ES是如何帮我们完成NLP的任务的。在做NLP相关任务的时候,ES的相似度算法并不足以支撑用户的搜索,需要使用一些与语义相关的方法进...

6366
来自专栏腾讯数据中心

变频冷机在超低负载下如何安全又节能运行?

使用变频冷机是为了节能,节能的前提是“冷机处于非满载工况下运行”。但如果当冷机负载太低(低于30%以下),冷机不仅无法有效节能,甚至不能正常工作——此时冷机会反...

3882

扫码关注云+社区

领取腾讯云代金券