洛谷题单指南-状态压缩动态规划-P3959 [NOIP 2017 提高组] 宝藏
原题链接：https://www.luogu.com.cn/problem/P3959
题意解读：n个节点m条边的带权无向图，从任意一个点start开始遍历，每次已访问节点集合中选取一个点u，扩展一个未访问过的点v，扩展点v的代价是从start到u的深度 * u到v的权值，直到访问完所有节点，求所有方案中代价的最小值。
解题思路：
本题的搜索解法可以参考https://www.cnblogs.com/hackerchef/p/18733710
这里给出状压DP的解决方案。
从题意分析可知，最终扩展出的是一棵树，因为如果不是树，必然形成环，可以去掉环中的一条边，总代价变小。
由于树是按层来扩展的，从第i层扩展到第i+1层的最低代价可以计算出来，如此我们可以设计状态。
设f[i][j]表示当前扩展到第i层，前i层点的状态是j的最小代价。状态用二进制位是来表示包含哪些点，如1011表示包含点0,1,3。
设前i-1层的状态是k，设从状态a扩展到状态b的最小代价是cost[a][b]，那么有：
对于所有的状态k
f[i][j] = min(f[i][j], f[i-1][k] + cost[k][j])
前i-1层的状态必然是前i层状态的子集，可以通过枚举二进制的子集来优化时间：for(int k = j; k; k = (k - 1) & j)
另外，可以提前预处理出cost[a][b]。
初始化：对于起点x，f[0][1 << x] = 0，其余为INF。
结果：取f[][(1 << n) - 1]的最小值。
100分代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 12, INF = 0x3f3f3f3f;
int g[N][N];
int f[N][1 << N], cost[1 << N][1 << N];
int n, m, ans = INF;
void init()
{
for(int i = 1; i < 1 << n; i++) //枚举所有状态
{
for(int j = i; j; j = (j - 1) & i) //枚举所有i的子集
{
int k = i ^ j; //k表示从j到i最新扩展出的一层状态
//计算所有从i到k中所有点的最小代价，累加到cost[j][i]
for(int s = 0; s < n; s++)
{
if(k >> s & 1)
{
int tmp = INF;
for(int t = 0; t < n; t++)
{
if(j >> t & 1)
{
tmp = min(tmp, g[t][s]);
}
}
if(tmp == INF)
{
cost[j][i] = INF; //状态转移不合法
break;
}
else cost[j][i] += tmp;
}
}
}
}
}
void dp(int x)
{
memset(f, 0x3f, sizeof(f));
f[0][1 << x] = 0;
for(int i = 1; i < n; i++) //枚举所有深度
{
for(int j = 1; j < 1 << n; j++) //枚举所有状态
{
for(int k = j; k; k = (k - 1) & j) //枚举所有子集
{
if(cost[k][j] != INF)
f[i][j] = min(f[i][j], f[i - 1][k] + i * cost[k][j]);
}
if(j == (1 << n) - 1) ans = min(ans, f[i][j]);
}
}
}
int main()
{
cin >> n >> m;
if(n == 1) //只有一个点的情况
{
cout << 0;
return 0;
}
memset(g, 0x3f, sizeof(g));
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
u--, v--; //编号从0开始
g[u][v] = g[v][u] = min(g[u][v], w);
}
init();
for(int i = 0; i < n; i++) dp(i);
cout << ans;
return 0;
}