二分图

饿↘昏→图↗

~~所谓二分图，就是在图上二分~~

定义

我们把一个图划分为两个点集，使得每个点集内的点没有边直接相连，我们称这个图可以划分为一个二分图。

首先，如果一个图有奇环就不可能是二分图。（读者自行思考）

我们可以采取黑白染色的方法，考虑DFS，每经过一个点就切换颜色，然后检查是否有相邻同色的点对。

因为有两个监狱，所以不难想到二分图。

发现答案有单调性，考虑二分答案。

每次二分最大的怨气值，然后用二分图判定判断是否能达成。

~~二分二分图~~

首先删一条边不会产生新的环。（显然）

所以需要找到一条边，使删掉它之后没有奇环。

很显然就是所有奇环的交集。

所以可以使用树上差分来维护每条边被奇环覆盖的次数。

可能不那么专业。

在一个二分图中选取最多的边，且每条边的端点不重，这就是二分图的最大匹配。

匈牙利算法。

首先优先匹配没有匹配的点。

如果没有，则看每个被匹配过的点/匹配的点/是否有别的点可以匹配或者抢，我们称这个操作为抢（个人习惯）。

假如最后每个被抢的点都匹配了，此时答案就多了一。

我们发现将每个被抢的点和它原来的匹配点相连，可以组成一条路径，这就是增广路。

假如找到了一条增广路，就等效于两行前的内容，答案加一。

所以匈牙利算法的本质就是找增广路。

用 DFS 写，每个点尝试找一条增广路，每找到一条，答案加一。

大约是个板子，每排有两个位置就建两个点，连边时记得两个点都连上。

这题偏思维，和二分图关系不太大。

~~首先检查是不是二分图~~

首先跑一遍最大匹配检查是否有完美匹配。

不难发现当且仅当图中没有环时才有唯一的最大匹配。

找环应该都会吧……

注：此做法为当场口胡，不保证其正确性。