bzoj5412

题意

(n)个点的竞赛图,给定(k)个点,满足去掉k个点后图中不存在环,选择另外最小的点数,使得仅去除那些点,使得图内无环。

做法

(k)个点内部有环则无解,题目保证(Sackslash k)内无环
由于是个竞赛图,若我们将其定义为(A,B)两部分,内部的拓扑排序是唯一的
重标号一下,令(l_i=j)(A)内最小的位置(B_ilongrightarrow A_j)(r_i=j)(A)内最大的位置使得(A_jlongrightarrow B_i)
而我们最后选出来的集合中任意两点(x,y(xle y)),需要满足(r_x<l_y)

原文地址:https://www.cnblogs.com/Grice/p/12964811.html