题意
图上有 \(n\) 个点,且具有点权,点权保证互不相同,若两个点点权有倍数关系,则两点之间有一边,问你最少删去多少个点能使图变为二分图。
思路
因为如果 \(a\) 是 \(c\) 的倍数且 \(c\) 是 \(b\) 的个数,所以 \(a\) 是 \(c\) 的倍数。
由此可以看出,若 \(a\) 与 \(b\) 相连且 \(b\) 与 \(c\) 相连,那么 \(a\) 一定与 \(c\) 相连,这样一定会形成一个环,无法组成二分图。
可以将一个点 \(x\) 分成 \(x_{0}\) 和 \(x_{1}\),表示 \(x\) 的只有入度或只有出度。
那么目标是找出若干对不能同时选的点,在它们之间连边,能够保留的点数即为这个图的最大独立集。
这个貌似不好直接求,但发现原图本身是一个偏序集,因此可以将我们自己建的图也定向成偏序集,求它的最长反链。
但 \(x_{0}\) 和 \(x_{1}\) 不能一起选,则连边 \(x_{0}\rightarrow x_{1}\)。
若 \(a_{y}\) 是 \(a_{x}\) 的倍数,除了 \((x_{1},y_{0})\) 以外任意两点都不能一起选,连边 \(x_{0}\rightarrow y_{0},x_{0}\rightarrow y_{1},x_{1}\rightarrow y_{1}\)。
接下来跑 dinic。
标签:偏序,连边,个点,题解,CF1630F,倍数,Bipartite,rightarrow From: https://www.cnblogs.com/aub-unluck-beginning/p/18365757