Day44【最短路+欧拉回路】

反色刷

欧拉回路典中典 $trick$。

不难想到把白边拆成 $2$ 条，那么对于某个连通块，其最多会走一次回路，那就是欧拉回路（如果有两个回路显然可以合并在一起），所以对每个联通块分别判定其所有点的度数是否为偶数即可。

用并查集易维护，注意如果初始全为白就不操作。

丁香之路

$i,j$ 之间的最短路是 $|i-j|$，显然呐。

假设当前处理 $i$，问题相当于求一个 $i$ 到 $s$ 的欧拉路径。不妨把 $i$ 与 $s$ 连边，那么问题等价于从 $i$ 出发的欧拉回路，注意 $(i,s)$ 这条边不产生贡献。

考虑到欧拉图需满足如下两个性质：

• 对于 $\forall i，2\mid de{g}_i$
• 图联通

对于此题，我们先贪心的满足第一个性质（因为第二个性质难以入手啊）。

假设有一个点序列 { a 1 , a 2 , a 3 , . . . , a n } \{a_1,a_2,a_3,...,a_n\} {a1​,a2​,a3​,...,an​}，满足 $2\nmid de{g}_{a_i}$，我们很自然想到把 $a_{2i}$ 与 $a_{2i+1}$ 连边，因为度数总和为偶数，所以 $a$ 的长度为偶数，这种贪心方法肯定是可行的，然而这种方法一定是最优的吗？

不一定，因为我们要保证图联通，所以在保证边权和不变的情况下，我们要尽可能的连边，因此我们把 $a_{2i}$ 和 $a_{2i}+1$ 连边，一直连到 $a_{2i+1}-1$ 与 $a_{2i+1}$，这样相当于连了 $a_{2i+1}-a_{2i}$ 条边权为 $1$ 的边，然而却最大限度的促使了图联通。

满足第一个性质后，图仍有可能不连通，所以我们定义两个联通块之间的边权为分别从两个联通块中选出一个点的最小距离，跑一遍最小生成树，因为每个联通块都是一个欧拉图，所以合并起来后所有点的欧拉回路要加上 $MST\times 2$，这是显然的。

然而最坏情况下联通块的个数会达到 $n$，此时边的规模达到了 $n^2$，无法接受。不难发现，我们贪心保证度数均为偶数后，联通块之间有一个相对顺序，举个例子，有三个联通块分别为 $a,b,c$，那么有 $w(a,c)=w(a,b)+w(b,c)$，那么最终能成为最小生成树上的边只可能是相邻联通块之间的边。

此时边的规模缩减为 $n$，所以单次求解时间复杂度为 $n\log n$，总时间复杂度为 $O(n^2\log n)$，可以接受。

具体实现上，可以先把 $m$ 条给定边的两端点 $UnionSet$ 起来，再进行后续操作。

骑士游戏