题解：P5008 [yLOI2018] 锦鲤抄

songyuteng · 2025-11-15 11:19:15 · 题解

P5008 [yLOI2018] 锦鲤抄 题解

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

题目大意

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

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

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

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

解题思路

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

如果是有向无环图：

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

  如果有环：

  如果整个强连通分量没有来自外部的入边（即入度为 0 的强连通分量），那么你无法直接删除它里面的任何一个点，因为每个点都有来自环内其他点的入边。

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

Tarjan

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

代码