标签:图论-二分图

题意在 $N$ 点 $M$ 边的有向无环图中选出最多的点,要求这些点两两之间不能有路径相连。$N\le 200$ ,$M\le 30000$ 。题解路径可达的关系可以通过 $\text{Floyd}$ 传递闭包处理。剩下的问题即转化为:选出最多的点,要求这些点两两没有连边。如果把每个点分裂成两个点,形成二分图,就是标准的最大独立集问题。最大独立集 $= N - $ 最小点覆盖(最大匹配)。#...
题解 图论-二分图