P6628 [省选联考 2020 B 卷] 丁香之路
枚举每个终点，先向 \(s\) 额外加一条边，就等价于求最小的欧拉回路。（根据图的性质，不走重复路一定更优）
刚开始的 \(m\) 条边必定会组成一系列的连通块，我们还要加边使之联通。
又要满足无向图欧拉回路的性质。也就是每个点的度数为偶数。
你考虑直接 \(1\sim n\) 枚举，将 2 个奇数度数的点中间连边抵消即可。（这里是拆成 dis 条边作为最优方案的）
最后这个图仍然不是联通的。。。
搞错了，再来！
我们上面的操作是使得每个连通块内部变成欧拉回路，然后用 mst 使得这些欧拉回路的连通块联通。
标签：图论,联通,45,连通,回路,条边,Day44,欧拉 From： https://www.cnblogs.com/LCat90/p/18447596