D. 旅行图 题解

题目大意

给定一个 $n$ 个点、$m$ 条边的无向带权图（$1 \le n \le 15$，$0 \le m \le 2000$），图中可能包含重边和自环。要求找一条从顶点 $1$ 出发并回到顶点 $1$ 的回路，使得每条边至少经过一次，并且总长度最短。输出最短长度，若不存在则输出 $-1$。

---

问题分析

这是一个**中国邮差问题（Chinese Postman Problem）**的变种：

• 标准中国邮差问题：找一条经过所有边至少一次的最短回路（起点任意）。
• 本题：起点固定为顶点 $1$。

---

核心知识点

1. 欧拉回路：在无向图中，存在一条经过每条边恰好一次的回路当且仅当所有顶点的度数均为偶数。
2. 奇度顶点：度数为奇数的顶点个数一定是偶数（因为总度数和为偶数）。
3. 最短路径：需要预处理所有点对之间的最短距离（因为 $n \le 15$，可以用 Floyd-Warshall）。
4. 最小权完美匹配：在奇度顶点之间进行配对，使得添加的路径总长最小（可用状压 DP 实现）。

---

解题思路

1. 基本公式

设：

• 所有边的长度之和为 $S$
• 奇度顶点的集合为 $odd$，其大小为 $d$（$d$ 为偶数）

那么最短回路长度为：

$$\text{ans} = S + \min_{\text{完美匹配 }M \text{ of } odd} \sum_{(u,v) \in M} \text{dist}(u,v) $$

解释：

• 原图所有边必须至少走一次，贡献 $S$。
• 为了让所有顶点度数变偶，需要在奇度顶点之间添加额外路径（相当于重复走这些路径）。
• 每对 $(u,v)$ 添加的路径长度就是它们之间的最短距离 $\text{dist}(u,v)$。
• 我们需要找到一种配对方式，使得添加的总长度最小。

2. 起点固定为 $1$ 的影响

• 如果顶点 $1$ 是奇度顶点，它会被包含在匹配中。
• 如果顶点 $1$ 是偶度顶点，它不会被匹配，但回路仍然从 $1$ 出发并回到 $1$，这与欧拉回路的性质一致（欧拉回路可以以任意顶点为起点）。

因此，公式不需要修改。

3. 无解的情况

以下情况输出 $-1$：

1. $m = 0$：没有边，无法经过所有边（因为需要经过至少一次）。
2. 图不连通，且 $1$ 所在的连通分量不包含所有边。
3. 更严格地说：如果存在任意一条边，其某个端点无法从 $1$ 到达（通过有边的路径），则无解。

---

算法步骤

Step 1：读入数据并计算度数

• 对于普通边 $(x,y)$：$deg[x]++$，$deg[y]++$
• 对于自环 $(x,x)$：$deg[x] += 2$（自环贡献 $2$ 度）
• 累计总长度 $total\_len$

Step 2：预处理最短路径

因为 $n \le 15$，使用 Floyd-Warshall 算法：

$$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j]) $$

• 初始化 $dist[i][i] = 0$
• 对于每条边 $(x,y,w)$：$dist[x][y] = \min(dist[x][y], w)$，$dist[y][x] = \min(dist[y][x], w)$

Step 3：检查连通性

对于每条有边的边，检查其端点是否都能从顶点 $1$ 到达（通过有路径的边）。如果有任意一条边的某个端点无法从 $1$ 到达，则输出 $-1$。

Step 4：找出奇度顶点集合

$$odd = \{ i \mid deg[i] \text{ is odd} \}$$

设 $d = |odd|$，如果 $d = 0$，则答案为 $total\_len$。

Step 5：最小权完美匹配

使用状压 DP：

• 状态 $mask$：二进制表示已经配对的奇度顶点集合（$0 \le mask < 2^d$）
• $dp[mask]$：已经配对集合为 $mask$ 时的最小额外长度
• 初始化 $dp[0] = 0$，其余为 $+\infty$
• 转移：找到 $mask$ 中最低位的 $0$ 对应的顶点 $i$，枚举另一个未配对的顶点 $j$：

$$dp[mask | (1 \ll i) | (1 \ll j)] = \min(dp[mask | (1 \ll i) | (1 \ll j)], dp[mask] + dist[odd[i]][odd[j]]) $$

• 最终答案：$ans = total\_len + dp[(1 \ll d) - 1]$

Step 6：输出答案

如果 $ans$ 仍然为 $+\infty$（无法匹配），输出 $-1$；否则输出 $ans$。

---

时间复杂度

• Floyd-Warshall：$O(n^3) = O(15^3) = O(3375)$
• 状压 DP：$O(2^d \cdot d^2)$，其中 $d \le n \le 15$，最坏 $O(2^{15} \cdot 15^2) \approx 32768 \cdot 225 \approx 7.4 \times 10^6$
• 总复杂度完全在 0.5 秒内

---

示例验证

示例 1

3 3
1 2 1
2 3 1
3 1 1

• 度数：$deg(1)=2$, $deg(2)=2$, $deg(3)=2$
• $odd = \emptyset$，$total\_len = 3$
• 答案 $= 3$

示例 2

3 2
1 2 3
2 3 4

• 度数：$deg(1)=1$, $deg(2)=2$, $deg(3)=1$
• $odd = \{1, 3\}$，$total\_len = 7$
• 最短路径 $dist[1][3] = 3 + 4 = 7$
• 答案 $= 7 + 7 = 14$

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    
    vector<int> deg(n, 0);
    int total_len = 0;
    vector<tuple<int, int, int>> edges;
    
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--; y--;
        edges.emplace_back(x, y, w);
        total_len += w;
        
        if (x == y) {
            deg[x] += 2;
        } else {
            deg[x]++;
            deg[y]++;
            dist[x][y] = min(dist[x][y], w);
            dist[y][x] = min(dist[y][x], w);
        }
    }
    
    // Floyd-Warshall 求最短路径
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    
    // 检查连通性
    vector<bool> has_edge(n, false);
    for (auto [x, y, w] : edges) {
        has_edge[x] = true;
        has_edge[y] = true;
    }
    
    for (int i = 0; i < n; i++) {
        if (has_edge[i] && dist[0][i] >= INF) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    if (m == 0) {
        cout << -1 << endl;
        return 0;
    }
    
    // 找出奇度顶点
    vector<int> odd;
    for (int i = 0; i < n; i++) {
        if (deg[i] % 2 == 1) odd.push_back(i);
    }
    
    int d = odd.size();
    if (d == 0) {
        cout << total_len << endl;
        return 0;
    }
    
    // 状压 DP 求最小权完美匹配
    vector<int> dp(1 << d, INF);
    dp[0] = 0;
    
    for (int mask = 0; mask < (1 << d); mask++) {
        if (dp[mask] >= INF) continue;
        
        // 找到第一个未匹配的顶点
        int i = -1;
        for (int t = 0; t < d; t++) {
            if (!(mask >> t & 1)) {
                i = t;
                break;
            }
        }
        if (i == -1) continue;
        
        // 枚举另一个未匹配的顶点 j
        for (int j = i + 1; j < d; j++) {
            if (!(mask >> j & 1)) {
                int new_mask = mask | (1 << i) | (1 << j);
                int add = dist[odd[i]][odd[j]];
                if (add < INF) {
                    dp[new_mask] = min(dp[new_mask], dp[mask] + add);
                }
            }
        }
    }
    
    int ans = total_len + dp[(1 << d) - 1];
    if (ans >= INF) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}

---

总结

本题的核心是将问题转化为中国邮差问题：

1. 计算所有边权和 $S$
2. 找出奇度顶点
3. 在奇度顶点之间做最小权完美匹配
4. 答案为 $S$ + 匹配长度

由于 $n \le 15$，可以使用 Floyd-Warshall 预处理最短路，再用状压 DP 求解最小权完美匹配。