這是狀壓DP中常見的一類問題(TSP問題)（廢話）

題目大意：

給你一個n+1個點的有向完全圖，現(xiàn)在要你從0號節(jié)點出發(fā)走過1-n號點至少一次，再返回0號點的最少時間，1<=n<=10

題意分析：

由于題目給出的是有向完全圖并且以鄰接矩陣的形式給出，所以我們先floyd預(yù)處理出最短的路徑

設(shè)狀態(tài)dp [ state ] [ i ]表示從0出發(fā)，走完state中的所有的點，最后停在i點的最短距離

枚舉 i 點之前的一個停留點 j ，得到如下的狀態(tài)轉(zhuǎn)移方程:

dp [ state ] [ i ] = min { dp [ state' ] [ j ] + dis [ i ] [ j ] }

其中 state' 是 state 去掉 i 點的集合 ， state必然包含 i 和 j

我們嘗試證明上述方程的正確性：

每次從子集中轉(zhuǎn)移，那么每次轉(zhuǎn)移時，每個子集都有答案，就是正確的

邊界：dp [ { i } ] [ i ] = dis [ 0 ] [ i ]

最后輸出最后的狀態(tài)到0點的最小代價即可

/* A - Hie with the Pie */ /* TSP問題，狀壓DP，狀態(tài)表示去過的城市 */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> int n; int dis[15][15]; /* 第一維表示狀態(tài)，第二維表示要到的城市 */ int dp[1 << 12][15];int main() {while (~scanf("%d", &n) && n){std::memset(dis, 0, sizeof(dis));std::memset(dp, -1, sizeof(dp));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++) /* Floyd跑最短路，預(yù)處理 */for (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++)dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);dp[1][0] = 0; /* 邊界 */for (int i = 1; i < (1 << (n + 1)); i++) /* 狀態(tài)枚舉 */{i |= 1;for (int j = 0; j <= n; j++)if (dp[i][j] != -1)for (int k = 0; k <= n; k++)if (j != k && (dp[i | (1 << k)][k] == -1 || (dp[i | (1 << k)][k] > dp[i][j] + dis[j][k])))dp[i | (1 << k)][k] = dp[i][j] + dis[j][k];}std::cout << dp[(1 << (n + 1)) - 1][0] << '\n';} }

轉(zhuǎn)載于:https://www.cnblogs.com/wyctstf/p/11341552.html

總結(jié)

以上是生活随笔為你收集整理的[POJ 3311] Hie with the Pie的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。