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