偶遇帝皇实力恐怖如斯，拼尽全力未能战胜

Graygoo · 2024-12-24 11:47:12 · 题解

vp 赛后两分钟过题。

先解决一些简单的部分。比如跑个 \text{tarjan} 就成了 DAG 上的问题。

我不是天赋哥，所以遇到这种一眼流肯定不能硬想，得尝试调用一下记忆库。

你在做过的流套路里进行一个检索，显然发现最接近的是 DAG 最小链覆盖。

当然这里显然还是可重的。众所周知原问题的可重版本有两种做法，一个是传递凹包，一个是 n+i 向 i 连 \inf 边。前面那个过于的 low，所以我们选择后一种方法。

显然源点连向每个点的流量是多少是重要的。考虑原问题相当于所有点的 a_i 都为 0 的情况，此时这个流量为 1，所以我们可以猜测，该问题中流量为 a_i + 1。

再考虑到一个简单事实，就是最后匹配的“链头”不能被其它点贡献，因此我们允许每个点有一个流量花费一点费用从出点走到自己的入点。

现在我们可以进行一个简单的思维模拟。你从 i 点出发，有一个流量和自己匹配，其余所有流量都走到了新点 j，其中一个流量和 j 匹配，剩下来一个通过反边走到这个点的出点。此时 j 的出点拥有的流量为 a_i - 1 + a_j + 1 = a_i + a_j，这个数字和我们想要的组合意义是一致的。因此这个过程可以不断进行下去，同时将链上经过的所有点都加入匹配。

这样的话跑一下最小费用最大流即可，是否有解即为最大流是否为 scc 个数。

你交一下，发现 WA 了。考虑到 a_i = 0 的点不可能当链头，所以 a_i = 0 的点不能向自己的入点连边。修改一下即可通过。