网络流 —— 从入门到入土

发布于 2019-03-16  334 次阅读


最大点独立集

前置要求:二分图最大匹配。

二分图最小顶点覆盖

定义:假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。
最小顶点覆盖=二分图的最大匹配数

二分图的最大独立集

定义:选出一些顶点使得这些顶点两两不相邻,则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
最大独立集=所有顶点数-最小顶点覆盖

二分图的最大团

定义:对于一般图来说,团是一个顶点集合,且由该顶点集合诱导的子图是一个完全图,简单说,就是选出一些顶点,这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说,我们默认为左边的所有点之间都有边,右边的所有顶点之间都有边。那么,实际上,我们是要在左边找到一个顶点子集X,在右边找到一个顶点子集Y,使得X中每个顶点和Y中每个顶点之间都有边。
方法:二分图的最大团=补图的最大独立集。

最大权闭合子图

定义:有一个有向图,每一个点都有一个权值(可以为正或负或0),选择一个权值和最大的子图,使得每个点的后继都在子图里面,这个子图就叫最大权闭合子图。

带上下界的网络流

前置要求:一般网络流的dinic算法。


血まみれからの方がさ,勝つ時にはカッコイイだろう.