二分图

本文章仅记录学习过程和例题，不再详细介绍二分图。

二分图的定义

简单的来说，就是把所有点分成左右两部分点，每部分内部没有连边，两部分之间有连边。

二分图最大匹配

找到一个最大的边集，满足每个点最多有一个连接的边在边集中。

边集中边集的数量就是二分图最大匹配。

有 n 个点，m 条边，常见的解决二分图最大匹配的方式有：

1. 匈牙利算法，复杂度 O(nm)。
2. 网络流，复杂度 O(m \sqrt{n})。

想要将问题转化为二分图最大匹配，可以通过寻找“0 要素”和“1 要素”。

“0 要素”指的是节点能分成两种类型，且每种节点内部没有连边。

“1 要素”指的是一个节点最多匹配一条边到另外一种节点。

P5182 棋盘覆盖 - 洛谷

把棋盘进行黑白间隔染色，将格子分为了黑白两种类型；同时，一个骨牌不会占用两个相同颜色的格子，说明节点内部没有连边，符合“0 要素”。

一个骨牌能占用自己周围四个颜色不同的格子，且只能同时占用一个，符合“1 要素”。

所以按格子颜色分类成左右部点，遇到不能放置的地方就跳过，做二分图最大匹配。

P10937 車的放置 - 洛谷

把棋盘分成横坐标和纵坐标两部分。

一个车不能同时存在于两个不同的横坐标，符合“0 要素”。

一个车确定了横坐标后还需要确定一个纵坐标，且同时只有一个纵坐标能存在，符合“1 要素”。

按横纵坐标做二分图最大匹配。

二分图最小点覆盖

给定二分图，求出一个最小的点集，使得图中的任意一条边都至少有一个端点属于点集。

事实上，存在柯尼希定理指出：二分图最小点覆盖=二分图最大匹配。证明过程略。

想要将问题转化为二分图最小点覆盖，可以通过寻找“2 要素”。

“2 要素”指的是，每条边有两个端点，且至少选其一。

UVA1194 Machine Schedule - 洛谷

每个机器必须在两种模式之间选一个，符合“2 要素”。

按模式 A、B 建图，做二分图最小点覆盖。

P6062 [USACO05JAN] Muddy Fields G - 洛谷

每个泥地要么放上一块横着的板子，要么放上一块竖着的，符合“2 要素”。

二分图最大独立集

找到一个最大的点集，使得其中任意两点之间都没有边相连。

P10939 骑士放置 - 洛谷

发现询问有多少个骑士不能相互攻击，其实是求有多少个独立点。

补图转化思想，求有多少个能够相互攻击的骑士，其实和上文“车的放置”完全相同。

拿总点数减去不能放置的点再减去最大匹配，即可。

有向无环图的最小路径点覆盖

给定一张有向无环图，要求用尽量少的不相交的简单路径，覆盖所有点，这就是有向无环图的最小路径点覆盖。

我们建立一张二分图，对于 x \rightarrow y，连接 x \rightarrow y+n，最后得到的二分图叫做原图的拆点二分图。

事实上，存在 有向无环图的最小路径点覆盖=n-拆点二分图的最大匹配。

UVA1184 UVA1184 Air Raid - 洛谷

板子题，直接按照上述操作即可 AC。