题解：CF21D Traveling Graph

· · 题解

题意：

给定一个带权无向图，求从节点 1 开始遍历图上所有的边至少一次并回到 1 的边权最小值。无解输出 -1。图中可能有重边与自环。n \leq 15,m \leq2000,1\leq w\leq10000。

题解：

首先显然题意可以转化为求一条边权最小的路径可重的欧拉回路。

考虑对于简单的无向图，其存在欧拉回路的充要条件为图中不存在偶度点。考虑把这个结论搬到本题上，发现如果把重复经过同一条边看作把这条边复制了一遍再走复制后的新边，那么我们最终走的路径就是普通的欧拉回路了。于是问题转化为：在原图上复制若干条边，使得复制的边权最小且图中存在欧拉回路。

此时我们就能够运用刚刚的结论了。我们考虑把偶点的状态看成 0，把奇点的状态看成 1，于是复制一条边的贡献就是把该边连接的两点的状态异或了 1。我们需要把图中所有点的状态全部变为 0。注意到如果我们复制了图中的一条链，那么这条链只会对链的两个端点的状态产生贡献，所以我们直接先用 Floyd 求出所有点对间的最短路，然后直接暴力枚举所有能完全将状态为 1 的点配对的方案，一个方案的答案就是原图中所有边权加上所有配对点间的最短路，求出所有方案的最小值即可。

注意一定是能完全匹配上的，因为奇点的个数一定是偶数。证明可以考虑每一条边都会使全图度数和加二，所以全图度数和是偶数，进而容易得到全图所有奇点的度数和也是偶数。故奇点的个数是偶数。

判断无解是简单的。