P5008 [yLOI2018] 锦鲤抄题解

闲话： 背景很感人，是为数不多的有故事而且有情感的好题（我很喜欢，但题目名字可以改一改）。

题目大意

如果抛开背景不谈，那么题目可以变为：

给出

n

个点

m

条边的一张有向无环图，每个点有一个点权值。

你每次可以选择一个有入度的点获取其点权然后删除这个点。

求能取

k

次的情况下最大能获得的权值和。

前言： 没学过 Tarjan 的建议先去学一学，很有用的。

入度为 $0$ 的点可以直接删。
如果点 $x$ 连向点 $y$ ，并且 $x$ 和 $y$ 我们都想删除，那么我们肯定是先删除 $y$ 再删除 $x$ ，否则删 $x$ 时 $y$ 还有入边（来自 $x$ ）就不能删。

如果整个强连通分量没有来自外部的入边（即入度为

0

的强连通分量），那么你无法直接删除它里面的任何一个点，因为每个点都有来自环内其他点的入边。

为了打破这个僵局，你必须至少保留这个强连通分量中的一个点不删除（这样其他点才能按顺序删掉，为了权值和最大，我们保留权值最小的那个点）。

Tarjan 算法可以把有向图的所有强连通分量（SCC）找出来，并且把每个 SCC 缩成一个点，形成一个新的 DAG（称为缩点图），这样就可以了，是不是很有用？