题意:$n$ 个点 $m$ 条边的有向图,带点权,每次可以选择一个有入度的点连同它的出边一起删除,并得到它的点权。可以重复这个过程至多 $k$ 次,求最终得到的最大权值和。

先考虑在更为简单的 DAG 图上进行操作。

很明显,我们只要像拓扑排序一样,任选一些入度不为 0 的点,然后按拓扑序从后往前选择,就可以满足题意。

所以在 DAG 上,我们只需要选 $k$ 个入度不为 0 的 权值最大的点,就可以做到了。

于是考虑怎么把原问题转换为在 DAG 上的问题。

对于有向图很自然的一个想法就是用强连通分量缩点。

如果一个强连通分量有入度,那显然这个分量里的任意一个点都可以选。

考虑一个没有入度的强连通分量如下图。

对于 (1→2→3→4→5→1) 这个强连通分量,不管按什么顺序选择,最后总会剩下一个点不能被选。

显然这个点的权值最小的时候答案最优。

于是我们就对于每一个入度为 0 的强连通分量寻找其中一个权值最小的点,然后剩下的点就可以任意选择了。

sort 就完事了。

不知道为啥我 sortnth_element 慢不了多少甚至还要快一点...

完整代码Link

最后修改:2021 年 03 月 25 日 07 : 43 PM