P10044 [CCPC 2023 北京市赛] 最小环

· · 题解

首先是标解，由于太简明直白就放前面了。

入度为 0 或出度为 0 的点一定不会在环上，这样的点可以直接删掉，那么度数（入度加出度）至少为 2。

而当入度等于出度等于 1 时，可以把这个点和入度出度这两条边合成一条边，这样并不改变环的存在与长度。

这样可以保证度数至少为 3，一条边只贡献 2 的度数，由于点的度数可以比 3 大，最后得到的新图我们根据度数有不等式 2m\ge 3n。

上述操作始终不会改变 m-n\le 1500 的事实（删点必定伴随删边，弱联通也是一个重要条件），解不等式组得到 n\le 3000,m\le 4500。

于是我们可以用传统的全源最短路+枚举边来找最小环，复杂度可以浅浅的做到 O(nm\log m)，此处 n,m 均为新图，也就是上述不等式得到的点数边数。

以下为我们队在此题下进行的讨论，没有标解这么直接，但也没标解这么跳跃，最后得到本质相同的办法，也算是正解。（更重要的是，这是考场思维，但我队友没打出来，这是可以说的吗

首先有向环一定处于强连通分量中，于是我们先跑个 tarjan 对每个强连通分量进行考察。

随意取一颗外向生成树，发现一些没用的性质，比如叶子必定有非树边使其强连通，非树边数 k 同样有 \le 1500 的条件。

但这些条件让我们感受到，点多叶子少，树边一定形成很多长链，于是我们考虑缩链，对于没有分叉也没有非树边的长链直接合成一条边，也就是由于非树边得到的一些点集，我们直接跑虚树，那么虚树边就自然进行了合并。

注意到非树边之和才为 1500，于是可以对每个强连通块的虚树（以及其非树边）跑全源最短路求最小环，\sum 起来复杂度也是 3000 同级别的 O(nm\log m) 可以接受。

然后吐槽一下已有题解，第一篇思路大概和咱考场相同，但是边双确实不严谨，最后用线段树优化也不是很懂。虚树的思想差不多，但最后应该和标解一样走合并度为 2 的点的路子，但前面思路都一样应该是正解。

然后是第二篇：

实际上，这样的操作并不能保证图的规模是 O(m-n)。

属实难蚌了，“忘记缩入度为 0 出度为 1 的点”也很难蚌，好好的全源最短路，搞什么去重边（不过自环确实是值得注意的点，特判即可），还有当前最优化的剪枝，我直接写标解也妹卡常啊，priority_queue 直接摆上去都不会T（一眼顶针鉴定为纯纯的乱搞）

而且跑每个强连通块既避免了出入度为 0 的特殊情况，同时每个块的全源最短路分开跑，常数会更小，就是难写点。

我写标解 20min 秒了！code。