网络流应用

刷了一天最大流的题,都快刷晕了,,

简单总结几个模型吧。

大部分内容来自学姐的PPT

拆点

一个非常有用的思想 限流 将对点的限制转化为对边的限制

点的合并

这个还没看到

最小割

最小割==最大流

一条增广路中,必有一条边满流,满流的流量即为这条增广路的流量,那么删除满流的这条边即可阻断一条增广路。删去一些边使源汇不连通即阻断所有的增广路,代价之和即为最大流。

最大流=最小割 你能想到什么?

大与小的转换 留下最多与拿走最少的转换 最大收益与最小损失的转换 选最优与不选最差的转换

什么时候转换? 凭直觉,看经验

最大流,每条增广路流量实际上是增广路上的最小流量

INF边

不会割掉不合法方案 使不合法方案经过inf边,从而保证割出的方案合法

对偶图

还没看

点覆盖集

点覆盖集是无向图 的一个点集,使得该图中所有边都至少有一个端点在该集合内。 最小点覆盖集是在无向图中,点数最少的点覆盖集。 最小点权覆盖集是在带点权无向图中,点权之和最小的点覆盖集。

最小点覆盖集=二分图最大匹配数 证明: 边分为匹配边和未匹配边 未匹配边一定至少有一个点被选中,否则会增加一个新的匹配,与最大匹配不符

最小点权覆盖=二分图最小割 证明: 把每一个匹配看做一条增广路,那么就是选一些点,使剩下的点两两之间无法连通,即割一些点使图不连通,即最小割

点独立集

点独立集是无向图 的一个点集,使得任两个在该集合中的点在原图中都不相邻。 最大点独立集是在无向图 中,点数最多的点独立集。 最大点权独立集是在带点权无向图中,点权之和最大的点独立集。

最大点独立集=V-最小点覆盖集 最大点独立集=V-二分图最大匹配数 证明: 1、当删去最小覆盖集时,剩下的点一定不会有连边,即剩下的点在原图中一定不相邻,所以最大点独立集至少包含非最小点覆盖集的所有点 2、点覆盖集已经是最小,即最小点覆盖集中如果再删去点v,v必将和独立集中的点有边相连,不符合独立集的概念,所以最大点独立集至多包含非最小点覆盖集的所有点 3、综上所述,最大点独立集=V-最小点覆盖集

最大点权独立集=总点权-最小点权覆盖集 最大点权独立集=总点权-二分图最小割

最大流——最小割 最大点独立集——最小点覆盖集

路径覆盖

路径覆盖就是在一个DAG(有向无环图)中找一些路经,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联。 最小路径覆盖就是最少的路径条数的路径覆盖。

最小路径覆盖=V-二分图最大匹配数 证明: 若匹配数为0,因为每个点都是一条路径,所以最小路径覆盖数为V; 当有一个匹配出现时,路径数就减1

边覆盖

边覆盖集是无向图的一个边集,使得该图中所有顶点都至少是集合内边的一个端点。

最小边覆盖集是在无向图中,边数最少的边覆盖集。 最小边覆盖=最大点独立集

闭合子图

有向图的闭合子图是一个点集,该点集的所有出边都还指向该点集 闭合子图中,点权和最大的点集称为最大权闭合子图

正点权和-最小割

最大密度子图

没看

01分数规划

没看

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2017.7.21夏令营清北学堂解题报告

预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票! T1: 题目描述 从前有一个?...

29360
来自专栏Java 源码分析

枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这...

32460
来自专栏潇涧技术专栏

Problem: Delete Number Problem

这题可以使用贪心策略,每次从高位向低位数,删除高位比低位数字小的那位上的数字,直到删除了k位之后,得到的数字肯定是最大值。

9720
来自专栏章鱼的慢慢技术路

Go指南练习_循环与函数

25620
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

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

数据挖掘知识脉络与资源整理(十)–箱线图

? ? 箱线图的简介 箱形图(Box-plot)又称为盒须图、盒式图或箱线图,是一种用作显示一组数据分散情况资料的统计图。因形状如箱子而得名。在各种领域也经常...

35280
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

11930
来自专栏PHP在线

PHP CodeBase: 生成N个不重复的随机数

有25幅作品拿去投票,一次投票需要选16幅,单个作品一次投票只能选择一次。前面有个程序员捅了漏子,忘了把投票入库,有200个用户产生的投票序列为空。那么你会如何...

34950
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

35360
来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

35740

扫码关注云+社区

领取腾讯云代金券