# 奇度顶点的最小费用配对

出题人解法：树的往返特判、奇度顶点间最短路、子集最小完美配对。Codex（GPT-6）：可移植实现、完整证明、边界与独立覆盖状态验证。首选程序为 [std.cpp](std.cpp)。

## 起点和特殊情况

任何覆盖全部边的闭合行走也访问全部顶点，因为图连通。把行走从其中任意顶点处循环移位，不改变费用，所以所有顶点的最优值相同，第一行恒为1。

若图是树，每条边都是桥。闭合行走跨过桥后必须跨回来，每条边至少使用两次；树边往返达到下界，所以答案为全部边权之和的两倍。这一步必须提前处理，因为树可能有远多于20个奇度顶点。

若所有顶点度数为偶数，连通图有欧拉回路，所有边各用一次即可，答案为边权之和。

## 把额外行走变为奇点配对

先计入每条边一次，费用为 $S$ .额外经过的边可以看成增加的重边。最终每个顶点度数必须为偶数，所以额外多重图的奇度点恰好是输入图的奇度点集合 $O$ .其数量 $k$ 为偶数，非树时 $k\le20$ .

任何这样的额外多重图都能分解成两两连接奇点的路径以及若干闭路。由于权非负，闭路费用非负；每条配对路径费用不小于两端最短距离。因此任何解的额外费用都至少是奇点最小完美配对费用。

反过来，取一个最优奇点配对，给每对奇点添加一条最短路径的边。内部顶点增加偶数度，配对端点各增加一次奇度，所有顶点都变为偶度。图仍连通，因此存在欧拉回路，达到 $S$ 加配对费用的下界。重复路径共享边也不影响这个多重图论证。

## 计算最短路与配对

从每个奇点跑 Dijkstra，记录任意两个奇点的距离 $d_{ij}$ .零权边合法，过期堆条目直接跳过。

令 $F(M)$ 为位集合 $M$ 中顶点的最小配对费用，$F(0)=0$ .选 $M$ 中编号最小的顶点 $i$ ，枚举它的伙伴：

$$F(M)=\min_{j\in M\setminus\{i\}}\left(d_{ij}+F(M\setminus\{i,j\})\right).$$

所有完美配对中，$i$ 都恰有一个伙伴；枚举覆盖全部选择且不会漏解。按掩码升序计算，因为删除位后掩码更小。奇数大小状态保持无穷，最终使用全体奇点对应的偶数状态。空奇点集合自然返回零。

## 复杂度与检验

时间 $O(k(n+m)\log(n+1)+k2^k)$ ，空间 $O(n+m+k^2+2^k)$ ；树分支为 $O(n+m)$ .使用64位距离和费用，虽然本题最优费用不超过两倍总边权、即 $4\cdot10^8$ ，宽类型使无穷值运算更直接。

小规模验证直接在“当前顶点、已覆盖边的集合”上跑最短路，独立于奇点配对模型。正式数据覆盖任意奇点数的树、重边欧拉图、20个奇点、零权、桥与环上弦。环上弦的数据另用二度链压缩后 Floyd 求距离，与完整图 Dijkstra 比较。

## 验证与性能

正式数据各运行五次，并单独测量峰值内存。标准程序最慢中位数 0.584849 秒，峰值 21.16 MiB。按2倍向上取整至0.5秒，参考时限为 1.5 秒。

[测试说明](tests/README.md)、[环境](../../../docs/评测环境与性能.md)及[逐次测量和哈希](../../../docs/benchmark-R35.json)提供复现依据。其他环境需重新校准。