单向TSP。 给一个m行n列(m<=10,n<=100)的整数矩阵,从第一列 任何一个位置出发每次往右,右上或右下走一个,最终到达最后一列,要求经过的整数之和最小整个矩阵是环形的,即第一行的上一行是最后一行,最后一行的下一行是第一行,输出路径上每列的行号,多解释输出字典序最小的。 输入: 第一行为两个整数M和N,分别表示矩阵的行数和列数。 接下来的M行,每行N个正整数,其中第i行第j列的整数表示矩阵的第i行第j列的元素。 输出:第一行为最小权和的路径,第二行为该路径的权和。路径由N个整数组成(相邻整数间用一个空格分开),表示路径经过的行号。如果权和最小的路径不止一条,输出字典序最小的一条。写出c++代码
时间: 2024-03-27 14:42:05 浏览: 15
此题可以使用动态规划求解,我们定义dp[i][j]表示从第i行第j列出发到达最后一列的最小权和路径,那么转移方程如下:
dp[i][j] = min(dp[i-1][(j-1+n)%n], dp[i][(j-1+n)%n], dp[i+1][(j-1+n)%n]) + matrix[i][j];
其中n为列数,%n是为了实现环形。
最后路径的输出可以使用回溯法。
下面是C++代码:
相关问题
9.单向TSP。 给一个m行n列(m<=10,n<=100)的整数矩阵,从第一列 任何一个位置出发每次往右,右上或右下走一个,最终到达最后一列,要求经过的整数之和最小整个矩阵是环形的,即第一行的上一行是最后一行,最后一行的下一行是第一行,输出路径上每列的行号,多解释输出字典序最小的。 输入: 第一行为两个整数M和N,分别表示矩阵的行数和列数。 接下来的M行,每行N个正整数,其中第i行第j列的整数表示矩阵的第i行第j列的元素。 输出:第一行为最小权和的路径,第二行为该路径的权和。路径由N个整数组成(相邻整数间用一个空格分开),表示路径经过的行号。如果权和最小的路径不止一条,输出字典序最小的一条。
解题思路:
此题可以转化为一个单向TSP问题,可以使用动态规划来解决。设f(i,j)表示从第i列第j行出发到达最后一列的最小权和路径长度,那么最终答案就是min{f(i,1)},其中1<=i<=m。由于是环形,因此需要特别处理第一列和最后一列的情况。
具体的转移方程如下:
f(i,j)=min{f(i+1,j-1),f(i+1,j),f(i+1,j+1)}+a[i][j],其中a[i][j]表示第i行第j列的元素。
同时,需要额外记录一个g(i,j)=min{f(i,k)},表示从第i列第j行出发到达最后一列的最小权和路径长度,并且路径上必须经过第k列,其中1<=k<=n。这样可以在输出路径时保证字典序最小。
代码实现如下:
单向TSP。 给一个m行n列(m<=10,n<=100)的整数矩阵,从第一列 任何一个位置出发每次往右,右上或右下走一个,最终到达最后一列,要求经过的整数之和最小整个矩阵是环形的,即第一行的上一行是最后一行,最后一行的下一行是第一行,输出路径上每列的行号,多解释输出字典序最小的。 输入: 第一行为两个整数M和N,分别表示矩阵的行数和列数。 接下来的M行,每行N个正整数,其中第i行第j列的整数表示矩阵的第i行第j列的元素。 输出:第一行为最小权和的路径,第二行为该路径的权和。路径由N个整数组成(相邻整数间用一个空格分开),表示路径经过的行号。如果权和最小的路径不止一条,输出字典序最小的一条。写出c++代码
以下是C++代码,使用了动态规划的思想,时间复杂度为O(m*n^2):
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 12;
const int MAXM = 102;
int m, n, a[MAXN][MAXM], dp[MAXN][MAXM][3], pre[MAXN][MAXM][3];
void output(int i, int j) {
if (j == n) {
cout << i << endl;
return;
}
int k = pre[i][j][1];
output(k, j+1);
cout << i << " ";
}
int main() {
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
int inf = 1e9;
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= m; i++) {
dp[i][1][1] = dp[i][1][0] = a[i][1];
}
for (int j = 2; j <= n; j++) {
for (int i = 1; i <= m; i++) {
for (int k = -1; k <= 1; k++) {
int ii = (i+k+m-1)%m+1;
if (dp[i][j][0] > dp[ii][j-1][0]+a[i][j]) {
dp[i][j][0] = dp[ii][j-1][0]+a[i][j];
pre[i][j][0] = ii;
} else if (dp[i][j][0] == dp[ii][j-1][0]+a[i][j]) {
pre[i][j][0] = min(pre[i][j][0], ii);
}
if (dp[i][j][1] > dp[ii][j-1][1]+a[i][j]) {
dp[i][j][1] = dp[ii][j-1][1]+a[i][j];
pre[i][j][1] = ii;
} else if (dp[i][j][1] == dp[ii][j-1][1]+a[i][j]) {
pre[i][j][1] = min(pre[i][j][1], ii);
}
if (dp[i][j][2] > dp[ii][j-1][2]+a[i][j]) {
dp[i][j][2] = dp[ii][j-1][2]+a[i][j];
pre[i][j][2] = ii;
} else if (dp[i][j][2] == dp[ii][j-1][2]+a[i][j]) {
pre[i][j][2] = min(pre[i][j][2], ii);
}
}
}
}
int ans = inf, st = 0;
for (int i = 1; i <= m; i++) {
if (dp[i][n][0] < ans) {
ans = dp[i][n][0];
st = i;
} else if (dp[i][n][0] == ans) {
st = min(st, i);
}
if (dp[i][n][1] < ans) {
ans = dp[i][n][1];
st = i;
} else if (dp[i][n][1] == ans) {
st = min(st, i);
}
if (dp[i][n][2] < ans) {
ans = dp[i][n][2];
st = i;
} else if (dp[i][n][2] == ans) {
st = min(st, i);
}
}
output(st, 1);
cout << endl << ans << endl;
return 0;
}
```