poj 3311(状压DP+最短路)

poj 3311
经典TSP问题,之前做的时候被虐,现在来做就是一道水题。
设$dp(S, i)$为状态$i$最后访问到$j$城市的最优解,那么有状态转移方程
$$dp(S, i) = min(dp(S-i, j), dis(j, i))$$
其中$j$是已经访问过的城市(即在$S$中),$dis$是两点最短路。
边界是$dp(S, i) = dis(0, i)$,当且仅当即只访问了点$i$
答案是$min(dp(E)(i) + dis(i, 0))$,其中$E$为$n$位$1$的二进制数(即全部访问)
注意图不是对称的,所以$dis(i, j)$是有序的,从$j$到$i$必须是$dis(j, i)$而不是$dis(i, j)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 10 + 5;
int n, dis[MAXN][MAXN], dp[1<<MAXN][MAXN]; //dp[st[i]][j] 设 状态i最后访问到j城市的最优解
void clean() {
ms(dis, 63), ms(dp, 63);
}
void solve() {
clean();
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++) scanf("%d", &dis[i][j]);
for (int k=0;k<=n;k++)
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++) if (k!=i&&k!=j&&i!=j) dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);//floyd
for (int S=1;S<(1<<n);S++) {//枚举每个状态
for (int i=1;i<=n;i++) {//枚举每个点
if (S&(1<<(i-1))) {//这个点在S中(已被访问)
if (S==(1<<(i-1))) {//如果S只访问了i
dp[S][i] = dis[0][i];//DP边界
} else {
for (int j=1;j<=n;j++) if (i!=j) {//找每个访问过的点j且这个点不是i
if (S&(1<<(j-1))) {
dp[S][i] = min(dp[S][i], dp[S^(1<<(i-1))][j] + dis[j][i]);
//图不对称所以必须是dis[j][i]而不是dis[i][j]
//找中间点更新值,类似floyd
}
}
}
}
}
}
int ans = 1000000000;
for (int i=1;i<=n;i++) ans = min(ans, dp[(1<<n)-1][i] + dis[i][0]);
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d", &n)==1&&n) solve();
return 0;
}

------ 本文结束 ------