题目回顾

Gord 正在为马拉松训练，他家后面有一个公园，公园里有多个水站和连接这些水站的慢跑路径。Gord 想要找到一条最短的慢跑路线，这条路线需要经过每条路径至少一次，并且起点和终点是同一个水站。

输入格式

• 每个测试用例的第一行包含两个正整数：n ≤ 15（水站的数量）和 m < 1000（路径的数量）。
• 接下来的 m 行，每行包含三个正整数：前两个表示路径连接的两个水站，第三个表示路径的长度（单位：cubits）。
• 输入以单独的一行 0 结束。

输出格式

对于每个测试用例，输出 Gord 的最短慢跑路线的长度。

解题思路

1. 问题分析：

   • 这是一个典型的“中国邮路问题”（Chinese Postman Problem），即在无向图中找到一条经过每条边至少一次的最短闭合路径。
   • 如果图中所有顶点的度数都是偶数，那么存在欧拉回路，最短路径就是所有边的长度之和。
   • 如果存在奇数度数的顶点，则需要通过添加一些边的重复遍历，使得所有顶点的度数变为偶数，然后计算最短路径。

2. 关键步骤：

   • 计算所有顶点的度数：统计每个水站的度数。
   • 找出奇数度数的顶点：这些顶点需要被配对，以确定需要重复遍历的路径。
   • 计算顶点之间的最短路径：使用 Floyd-Warshall 算法计算所有水站之间的最短路径。
   • 动态规划配对奇数度数的顶点：通过动态规划找到最优的配对方式，使得重复遍历的路径长度最短。
   • 计算总路径长度：原始路径长度之和加上重复遍历的路径长度。

标程

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define INF 1000000001
using namespace std;
typedef long long ll;

int read() {
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

int n, m, Ans, Top;
int F[32768], D[1005], Dis[16][16];
int St[16];

void Floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                Dis[i][j] = min(Dis[i][j], Dis[i][k] + Dis[k][j]);
}

void Input_Init() {
    m = read(); Ans = Top = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) if (i != j) Dis[i][j] = INF;
        D[i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        static int x, y, z;
        x = read(), y = read(), z = read();
        D[x]++; D[y]++;
        if (Dis[x][y] > z) Dis[x][y] = Dis[y][x] = z;
        Ans += z;
    }
}

void Solve() {
    for (int i = 1; i <= n; i++) if (D[i] & 1) St[++Top] = i;
    for (int i = 1; i < 1 << Top; i++) F[i] = INF;
    for (int i = 0; i < 1 << Top; i++) {
        int x = 1;
        while (1 << (x - 1) & i) x++;
        for (int y = x + 1; y <= Top; y++) if ((i & (1 << (y - 1))) == 0)
            F[i | (1 << (x - 1)) | (1 << (y - 1))] = min(F[i | (1 << (x - 1)) | (1 << (y - 1))], F[i] + Dis[St[x]][St[y]]);
    }
    printf("%d\n", F[(1 << Top) - 1] + Ans);
}

int main() {
    while (scanf("%d", &n) && n) {
        Input_Init();
        Floyd();
        Solve();
    }
    return 0;
}

代码解释

1. 输入处理：

   • read() 函数用于快速读取输入。
   • Input_Init() 函数初始化水站和路径的信息，计算每个水站的度数，并初始化邻接矩阵 Dis。

2. 最短路径计算：

   • Floyd() 函数使用 Floyd-Warshall 算法计算所有水站之间的最短路径。

3. 动态规划配对：

   • Solve() 函数找出所有奇数度数的顶点，并使用动态规划找到最优配对方式，使得重复遍历的路径长度最短。
   • F 数组用于存储状态，F[i] 表示状态 i 下的最小重复路径长度。

4. 输出结果：

   • 最终的最短路径长度为原始路径长度之和 Ans 加上重复遍历的路径长度 F[(1 << Top) - 1]。

复杂度分析

• 时间复杂度：
  • Floyd-Warshall 算法：O(n³)。
  • 动态规划配对：O(2^k * k²)，其中 k 是奇数度数的顶点数量（k ≤ 14）。
• 空间复杂度：
  • 邻接矩阵：O(n²)。
  • 动态规划数组：O(2^k)。

总结

通过计算水站之间的最短路径和动态规划配对奇数度数的顶点，可以高效地解决中国邮路问题，找到 Gord 的最短慢跑路线。代码逻辑清晰，适用于题目给定的输入规模。