P3199 HNOI2009 最小圈 题解

2025-12-15

题意:找有向图上平均值最大的环。 首先,看到平均值,可以想到分数规划。所以二分,判断是否有负环即可。 使用 dfs 判断,复杂度 $O(nm \log V)$