CSP-S 2022 假期计划 - 图论、动态规划 - OI竞赛 - 常规

CSP-S 2022 假期计划 - 图论与动态规划

题目描述

小熊的地图上有 $n$ 个点，点 $1$ 是家，点 $2, 3, ..., n$ 是景点。一些点对之间有直达的公交线路。小熊想从家出发，游玩 $4$ 个不同的景点并回到家，每段行程最多转车 $k$ 次。

给定每个景点的分数以及点之间的连接情况，要求找到一个行程安排，使得小熊访问的四个景点的分数之和最大。

解题思路

本题可以使用图论中的最短路算法和动态规划来解决。

1. 预处理：计算可达性

首先，我们需要预处理出任意两个景点之间是否可以在最多转车 $k$ 次的情况下到达。可以使用 Floyd 算法或 BFS 算法来实现。

Floyd 算法: 创建一个 $n imes n$ 的邻接矩阵 dist，其中 dist[i][j] 表示从点 $i$ 到点 $j$ 最少需要转车的次数。初始时，如果点 $i$ 和点 $j$ 之间有直达线路，则 dist[i][j] = 0，否则 dist[i][j] = k + 1。然后，枚举所有中间点 $k$，更新 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。* BFS 算法: 对每个点 $i$，进行一次 BFS 搜索，计算出从点 $i$ 出发，最多转车 $k$ 次可以到达的所有景点。

2. 动态规划

定义状态 dp[i][j][cnt] 表示当前位于景点 $i$，上一个访问的景点是 $j$，已经访问了 cnt 个景点的最大分数之和。

状态转移方程如下：

dp[i][j][cnt] = max(dp[i][j][cnt], dp[j][l][cnt-1] + score[i])

其中：

score[i] 表示景点 $i$ 的分数。* l 表示上一个访问的景点，需要满足 dist[l][i] <= k，即从景点 $l$ 到景点 $i$ 最多转车 $k$ 次可达。

最终答案为 max(dp[1][j][4])，其中 j 是任意一个可以到达家（点 $1$）的景点。

代码实现 (C++)cpp#include #include #include

using namespace std;

const int MAXN = 2505;const long long INF = 1e18;

int n, m, k;long long score[MAXN];int dist[MAXN][MAXN];long long dp[MAXN][MAXN][5]; // 注意数据范围，需要使用 long long

int main() { cin >> n >> m >> k; for (int i = 2; i <= n; ++i) { cin >> score[i]; }

// 初始化距离矩阵 memset(dist, 0x3f, sizeof(dist)); for (int i = 1; i <= n; ++i) { dist[i][i] = 0; } for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; dist[u][v] = dist[v][u] = 0; // 直接相连，距离为 0 }

// Floyd 算法计算最短路 for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } }

// 初始化 dp 数组 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { for (int cnt = 0; cnt <= 4; ++cnt) { dp[i][j][cnt] = -INF; } } } dp[1][1][0] = 0;

// 动态规划 for (int cnt = 1; cnt <= 4; ++cnt) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (dist[j][i] <= k) { // 判断景点 j 到 i 是否可达 for (int l = 1; l <= n; ++l) { if (j != l && dist[l][j] <= k) { dp[i][j][cnt] = max(dp[i][j][cnt], dp[j][l][cnt - 1] + score[i]); } } } } } }

// 寻找最大分数 long long ans = 0; for (int i = 2; i <= n; ++i) { if (dist[i][1] <= k) { ans = max(ans, dp[1][i][4]); } }

cout << ans << endl; return 0;}

复杂度分析

时间复杂度：Floyd 算法 $O(n^3)$，动态规划 $O(n^3 imes k)$，总时间复杂度为 $O(n^3 imes k)$。* 空间复杂度：$O(n^2)$。

总结

本题结合了图论中最短路的思想和动态规划的技巧，需要仔细分析题目条件，设计合理的状态和状态转移方程，才能高效地解决问题