题意
有一个 \(n\) 个点的 DAG，现在有 \(k\) 波进攻，第 \(i\) 波有 \(i\) 个人，它们每个人会选择一条 DAG 上的路径，并占领这个路径上的所有点，路径之间是不能相交的。第 \(i\) 波进攻前可以做一些准备，可以花 \(1\) 秒关闭某个点的所有入边，或关闭某个点的所有出边。第 \(i\) 波进攻有个参数 \(a_i,b_i\)，如果花费了 \(t_i\) 时间准备，如果不会所有点都被占领，就会获得收益 \(\max(0,a_i-tb_i)\)，如果被占领就不会有收益了，求最大收益，输出方案。
\(n \leq 50,1\le k\le n-1\)。
题解
将每个点拆为入点和出点，做二分图匹配，则覆盖所有点的最小路径数量 \(=n-\) 匹配数。
每次操作可以关闭某个点的所有入边或出边，就是在二分图中删去一个点。我们要求第 \(i\) 波时 \(n-\) 匹配数 \(>i\)。
而删去一个点，最多只会减少一个匹配。我们希望每次删点都减少一个匹配，能否做到？
设某个时刻二分图中点数为 \(m\)，初始 \(=2n\)。因为匹配数 \(=m-|S|\)，\(S\) 为最大独立集，所以只要我们每次删 \(\overline{S}\) 中的元素就可以做到。\(n-(2n-|S|)+(2n-|S|)=n\)，而 \(k\le n-1\)，所以可以做到。
每次删去的点地位相同，做一个简单的 \(\text{DP}\) 即可。复杂度 \(O(n^3)\)。
标签：le,匹配,题解,路径,CF1525F,删去,2n From： https://www.cnblogs.com/fish07/p/17303217.html