CF gym 103409E Buy and Delete 解题报告

CFgym103409E

Alice 和 Bob 在一个有向图上玩游戏，最开始有向图上没有边，Alice 先手买几条边加到图中，之后，Bob 需要从图中删边直到无边。但是 Bob 每次只能删掉一个边集 $S$ ，$S$ 必须是无环的。

有 $m$ 条边，Alice 最多可以买不超过 $c$ 条边，Alice 想要最大化删边轮数，Bob想要最小化删边轮数，两边都是最聪明的，请求出删边轮数。

$n \leq 2000,m \leq 5000$

显然没有环的情况下 Bob 可以一次性删去整张图，答案就是 1。

考虑有环的情况，实际上整张图有几个环都是一样的，因为 Bob 可以一次性删去所有环除了某条边以外的所有边，第二次删去一条边，故有环的情况下答案就是 2 。这样对于 Alice 来说其实多买几个环是没有意义的，所以我们只考虑一个环。根据贪心，我们判断一下图中的最小环权值是否 $\leq c$ 即可。

注意到这题实际上 $m$ 不大，所以可以用 Dijkstra 求最小环。

设 $u$ 和 $v$ 之间有一条边长为 $w$ 的边， 表示删除 $u$ 和 $v$ 之间的连边之后， $u$ 和 $v$ 之间的最短路。那么最小环是 $dis(v,u) + w$，时间复杂度 $O(m(n+m)\log n)$

Code