題目大意：給定一個(gè)有重邊，邊有權(quán)值的無向圖。從某一個(gè)點(diǎn)出發(fā)，求到達(dá)所有的點(diǎn)需要的最少費(fèi)用，并且限制兩點(diǎn)之間只有一條路徑。費(fèi)用的計(jì)算公式為：所有邊的費(fèi)用之和。而邊$x->y$的費(fèi)用就為：$y$到初始點(diǎn)的之間點(diǎn)的個(gè)數(shù)（包括起始點(diǎn)） $\times$ 邊權(quán)。

題解：狀壓$DP$，令$f_{i,j}$表示當(dāng)前深度為$i$，狀態(tài)為$j$的最小花費(fèi)

$$f_{i,s}=f_{i-1,t}+g_{s,t}\times(i?1)$$

再開一個(gè)數(shù)組$c_{s,i}表示狀態(tài)$s$挖到點(diǎn)$i$的最小花費(fèi)（不考慮深度）

用邊權(quán)更新$c$數(shù)組，再用$c$數(shù)組更新$g$數(shù)組即可

卡點(diǎn)：1.$c$數(shù)組第二維開太小

C++ Code：

#include <cstdio> #include <cstring> #define lb(x) (x & -x) #define maxn 13 using namespace std; const int inf = 0x3f3f3f3f; int n, m, U, ans = inf; int e[maxn][maxn], c[maxn][1 << maxn | 3]; int g[1 << maxn | 3][1 << maxn | 3], f[maxn][1 << maxn | 3]; inline void getmin(int &a, int b) {if (a > b) a = b;} inline int min(int a, int b) {return a < b ? a : b;} int main() {scanf("%d%d", &n, &m); U = 1 << n;if (n == 1) {puts("0");return 0;}memset(e, 0x3f, sizeof e);for (int i = 0; i < m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);e[a][b] = e[b][a] = min(c, e[a][b]);}for (int i = 1; i <= n; i++) {for (int j = 1; j < U; j++) {c[i][j] = inf;if (!(j & (1 << i - 1))) {for (int k = 1; k <= n; k++) {if (j & (1 << k - 1)) getmin(c[i][j], e[i][k]);}}}}for (int i = 1; i < U; i++) {for (int j = i & i - 1; j; j = i & j - 1) {int tmp = i ^ j;for (int k = 1; k <= n; k++) {if (tmp & (1 << k - 1)) {g[i][j] += c[k][j];if (g[i][j] > inf) g[i][j] = inf;}}}}memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++) f[1][1 << i - 1] = 0;for (int i = 2; i <= n; i++) {for (int j = 1; j < U; j++) {for (int k = j & j - 1; k; k = j & k - 1) {int tmp = inf;if (g[j][k] ^ inf) tmp = g[j][k] * (i - 1);if (f[i - 1][k] ^ inf) getmin(f[i][j], f[i - 1][k] + tmp);}}getmin(ans, f[i][U - 1]);}printf("%d\n", ans);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Memory-of-winter/p/9504801.html

總結(jié)

以上是生活随笔為你收集整理的[NOIP2017 TG D2T2]宝藏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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