题解：CF1630F Making It Bipartite

网络流毒瘤题。

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

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

设有两条边：

$a \rightarrow b \rightarrow c$。

那么根据倍数关系，则一定有一条边 $a \rightarrow c$。

此时无法二分染色。

据此可知，若一个点有入度、出度，则整个图一定无法成为二分图。

考虑套路拆点，把 $x$ 拆分为两个点：$x,x'$，分别代表出度、入度，那么目标是找出若干对不能同时选的点，在它们之间连边，能够保留的点数即为这个图的最大独立集。

但，图的最大独立集显然只能暴力。

吗？发现，原图是一个偏序集！此时，我们有 Dilworth 定理。

它给我们指明了方向——只要求出图的最长反链（即最小链覆盖）即可！就可以拆点跑网络流了！