PEEK143 郊区春游

题目链接

题目描述

给定一个由 $N$ 个郊区和 $M$ 条无向道路组成的城市地图，每条道路有通行费用。现在需要从中挑选 $K$ 个指定的郊区进行游玩。游玩顺序可以任意排列，但必须访问完所有 $K$ 个郊区。总费用等于游玩过程中，按顺序访问的相邻两个郊区之间的最短路径长度之和。请求出最小可能的总费用。

解题思路

本题的实质是寻找一个访问 $K$ 个指定节点的最优顺序，使得总路径成本最低。这是一个经典的旅行商问题 (Traveling Salesperson Problem, TSP) 的变体。由于 $K$ 的值很小（通常 $K \le 15$ ），我们可以使用状态压缩动态规划 (State Compression DP) 来解决。

核心步骤：

预处理：计算全源最短路
- 题目中的通行费用是任意两个游玩点之间的最短路径长度，而不是直接的边权。因此，第一步是计算出图中任意两个节点之间的最短距离。
- 我们可以使用 Floyd-Warshall 算法来计算全源最短路。该算法的时间复杂度为 $\mathcal{O}(N^3)$ ，在 $N$ 较小的情况下（如 $N \le 100$ ）是完全可行的。
- 在得到 $dist[u][v]$ 矩阵后，我们可以只关注 $K$ 个指定郊区之间的距离，相当于构建了一个新的、只包含这 $K$ 个点的完全图。
状态压缩 DP 求解 TSP
- 状态定义： $dp[S][i]$
  - $S$ : 一个 $K$ 位的位掩码 (bitmask)。 $S$ 的二进制表示中，第 $j$ 位为 1 代表第 $j$ 个指定郊区已经被访问过，为 0 则表示未访问。
  - $i$ : 当前路径的终点是第 $i$ 个指定郊区。
  - $dp[S][i]$ 的值：表示访问了 $S$ 中标记的所有郊区，并且以第 $i$ 个郊区作为结束点的最短路径总长度。
- 状态转移：
  
  为了计算 $dp[S][i]$ ，我们需要枚举路径中倒数第二个访问的郊区 $j$ 。这个 $j$ 必须是 $S$ 中除了 $i$ 之外的另一个郊区。
  - $dp[S][i] = \min(dp[S \oplus (1 \ll i)][j] + dist(p_i, p_j))$
  - 其中， $S \oplus (1 \ll i)$ 是一个位运算，表示从集合 $S$ 中去掉 $i$ 这个元素。 $p_i$ 和 $p_j$ 是第 $i$ 个和第 $j$ 个指定郊区的原始编号， $dist(p_i, p_j)$ 是它们之间的最短路程。
  - 这个转移方程的含义是：要到达状态 $(S, i)$ ，我们可以从任何一个已经访问了 $S$ 中除 $i$ 之外所有点、且终点为 $j$ 的状态 $(S \oplus (1 \ll i), j)$ 出发，然后从 $j$ 走到 $i$ 。
- 初始状态：
  
  对于所有 $K$ 个指定郊区，它们都可以作为旅行的起点。因此，对于第 $i$ 个指定郊区（ $0 \le i < K$ ）， $dp[1 \ll i][i] = 0$ 。这表示访问单个郊区 $i$ ，并以它为终点，路径长度为 0。
- 最终答案：
  
  在填充完整个 DP 表之后， $dp[(1 \ll K) - 1][i]$ 存储了访问完所有 $K$ 个郊区，并以第 $i$ 个郊区为终点的最短路径长度。我们只需要在所有可能的终点 $i$ 中取一个最小值，即 $\min(dp[(1 \ll K) - 1][i])$ for $0 \le i < K$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> p(k);
    for (int i = 0; i < k; ++i) {
        cin >> p[i];
    }

    vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));
    for (int i = 1; i <= n; ++i) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }

    // Floyd-Warshall 算法
    for (int l = 1; l <= n; ++l) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][l] != INF && dist[l][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
                }
            }
        }
    }

    // 动态规划
    vector<vector<int>> dp(1 << k, vector<int>(k, INF));

    for (int i = 0; i < k; ++i) {
        dp[1 << i][i] = 0;
    }

    for (int s = 1; s < (1 << k); ++s) {
        for (int i = 0; i < k; ++i) {
            if ((s >> i) & 1) { // 如果 i 在集合 s 中
                if (dp[s][i] == INF) continue;
                for (int j = 0; j < k; ++j) {
                    if (!((s >> j) & 1)) { // 如果 j 不在集合 s 中
                        int next_s = s | (1 << j);
                        int u = p[i];
                        int v = p[j];
                        if (dist[u][v] != INF) {
                            dp[next_s][j] = min(dp[next_s][j], dp[s][i] + dist[u][v]);
                        }
                    }
                }
            }
        }
    }

    int min_cost = INF;
    int final_state = (1 << k) - 1;
    for (int i = 0; i < k; ++i) {
        min_cost = min(min_cost, dp[final_state][i]);
    }

    cout << min_cost << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        int[] p = new int[k];
        for (int i = 0; i < k; i++) {
            p[i] = sc.nextInt();
        }

        int INF = 1_000_000_000;
        int[][] dist = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            dist[u][v] = Math.min(dist[u][v], w);
            dist[v][u] = Math.min(dist[v][u], w);
        }

        // Floyd-Warshall 算法
        for (int l = 1; l <= n; l++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][l] != INF && dist[l][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][l] + dist[l][j]);
                    }
                }
            }
        }

        int[][] dp = new int[1 << k][k];
        for (int i = 0; i < (1 << k); i++) {
            Arrays.fill(dp[i], INF);
        }

        for (int i = 0; i < k; i++) {
            dp[1 << i][i] = 0;
        }

        for (int s = 1; s < (1 << k); s++) {
            for (int i = 0; i < k; i++) {
                if ((s & (1 << i)) != 0) { // 如果 i 在集合 s 中
                    if (dp[s][i] == INF) continue;
                    for (int j = 0; j < k; j++) {
                        if ((s & (1 << j)) == 0) { // 如果 j 不在集合 s 中
                            int nextS = s | (1 << j);
                            int u = p[i];
                            int v = p[j];
                            if (dist[u][v] != INF) {
                                dp[nextS][j] = Math.min(dp[nextS][j], dp[s][i] + dist[u][v]);
                            }
                        }
                    }
                }
            }
        }

        int minCost = INF;
        int finalState = (1 << k) - 1;
        for (int i = 0; i < k; i++) {
            minCost = Math.min(minCost, dp[finalState][i]);
        }

        System.out.println(minCost);
    }
}

n, m, k = map(int, input().split())
p = list(map(int, input().split()))

INF = float('inf')
dist = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    dist[i][i] = 0

for _ in range(m):
    u, v, w = map(int, input().split())
    dist[u][v] = min(dist[u][v], w)
    dist[v][u] = min(dist[v][u], w)

# Floyd-Warshall 算法
for l in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if dist[i][l] != INF and dist[l][j] != INF:
                dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j])

dp = [[INF] * k for _ in range(1 << k)]

for i in range(k):
    dp[1 << i][i] = 0

for s in range(1, 1 << k):
    for i in range(k):
        if (s >> i) & 1:
            if dp[s][i] == INF:
                continue
            for j in range(k):
                if not ((s >> j) & 1):
                    next_s = s | (1 << j)
                    u, v = p[i], p[j]
                    if dist[u][v] != INF:
                        dp[next_s][j] = min(dp[next_s][j], dp[s][i] + dist[u][v])

min_cost = INF
final_state = (1 << k) - 1
for i in range(k):
    min_cost = min(min_cost, dp[final_state][i])

print(min_cost)

算法及复杂度

算法：Floyd-Warshall + 状态压缩动态规划。
时间复杂度：
- Floyd-Warshall 算法： $\mathcal{O}(N^3)$ 。
- 状态压缩 DP： $\mathcal{O}(K^2 \cdot 2^K)$ 。
- 总时间复杂度为 $\mathcal{O}(N^3 + K^2 \cdot 2^K)$ 。
空间复杂度：
- $dist$ 矩阵： $\mathcal{O}(N^2)$ 。
- $dp$ 表： $\mathcal{O}(K \cdot 2^K)$ 。
- 总空间复杂度为 $\mathcal{O}(N^2 + K \cdot 2^K)$ 。

题解 | #郊区春游#

PEEK143 郊区春游

题目链接

题目描述

解题思路

代码

算法及复杂度