图上投币 题解

思路

答案对权值阈值具有单调性。固定阈值 $x$，只保留 $a_i\le x$ 的顶点：若诱导子图有环，可无限绕行；若无环，可拓扑计算最长顶点数并判断是否至少为 $k$。

做法

子任务 1：枚举游走

从每个起点 DFS 枚举最多 $k$ 个顶点的全部游走，维护路径最大权值并取最小。

子任务 2：二值点权

答案只有 $1$、$2$ 或 $-1$。分别检查阈值 1 和 2，无需二分。

子任务 3：二分与拓扑 DP

对权值阈值二分。每次计算保留子图的入度并做 Kahn 拓扑排序，同时令 dp[v] 为以 $v$ 结尾的最长路径顶点数。未能处理全部保留顶点说明有环；否则检查最大 dp 是否至少为 $k$。

复杂度

枚举游走为 $O(n^k)$；二值点权为 $O(n+m)$；满分算法为 $O((n+m)\log 10^9)$，空间复杂度 $O(n+m)$。

正确性证明

引理 1　固定阈值下存在至少 $k$ 个顶点的游走，当且仅当保留子图有环或其 DAG 最长路径至少为 $k$。

证明　有环可重复绕行得到任意长度；无环时游走不能重复顶点，恰为一条路径，拓扑 DP 枚举其最大长度。∎

引理 2　阈值可行性单调不减。

证明　提高阈值只会加入顶点和边，原有可行游走仍存在。∎

定理　二分得到的值是最小可能最大权值。

证明　由引理 1 每次判定正确，由引理 2 可二分；所得最小可行阈值恰等于某条可行游走最大点权的最小值。∎