题解：CF1630F Making It Bipartite

· · 题解

网络流毒瘤题。

写题解前，要感谢此题让我发现之前的网络流板子假了！

思路

考虑如何才能判定二分图。

设有两条边：

那么根据倍数关系，则一定有一条边 $a \rightarrow c$。 此时无法二分染色。 据此可知，若一个点有入度、出度，则整个图一定无法成为二分图。 考虑套路拆点，把 $x$ 拆分为两个点：$x,x'$，分别代表出度、入度，那么目标是找出若干对不能同时选的点，在它们之间连边，能够保留的点数即为这个图的最大独立集。 但，图的最大独立集显然只能暴力。 吗？发现，原图是一个[偏序集](https://baike.baidu.com/item/%E5%81%8F%E5%BA%8F%E9%9B%86/4328855)！此时，我们有 [Dilworth 定理](https://baike.baidu.com/item/%E7%8B%84%E5%B0%94%E6%B2%83%E6%96%AF%E5%AE%9A%E7%90%86/18900593)。 它给我们指明了方向——只要求出图的最长反链（即最小链覆盖）即可！就可以拆点跑网络流了！ ## code [link](https://codeforces.com/contest/1630/submission/302339997)