/*
宝藏的子集dp做法 看起来还是很靠谱的
需要保存的状态就只有选择的状态和已选的最大深度
令f[S][i] 表示当前选择的生成树集合为S, 树高为i的最小花费
那么显然F[S][i] 可以从所有的 F[T \subset S][i - 1]转移而来, 我们暴力考虑将其连接上的点深度都是最深的, 这样虽然不一定是最优解, 但是总体上不会漏掉最优解
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
#define M 12
#define mmp make_pair
using namespace std;
int read() {
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
const int inf = 0x3e3e3e3e;
int dis[M][M], n, m, g[1 << M], f[1 << M][M + 1], note[M];
int main() {
n = read(), m = read();
memset(dis, 0x3e, sizeof(dis));
memset(f, 0x3e, sizeof(f));
for(int i = 1; i <= m; i++) {
int vi = read() - 1, vj = read() - 1, v = read();
dis[vi][vj] = min(dis[vi][vj], v);
dis[vj][vi] = min(dis[vj][vi], v);
note[vi] |= (1 << vj);
note[vj] |= (1 << vi);
}
for(int i = 0; i < n; i++) f[1 << i][0] = 0, note[i] |= (1 << i);
for(int s = 1; s < (1 << n); s++) {
for(int i = 0; i < n; i++) {
if(s & (1 << i)) {
g[s] = g[s ^ (1 << i)] | note[i];
break;
}
}
for(int t = (s - 1) & s; t; t = (t - 1) & s) {
if((g[t] | s) == g[t]) {
int tot = 0, ss = s ^ t;
for(int i = 0; i < n; i++) {
if(ss & (1 << i)) {
int tmp = inf;
for(int j = 0; j < n; j++) {
if(t & (1 << j)) {
tmp = min(tmp, dis[j][i]);
}
}
tot += tmp;
}
}
for(int j = 1; j < n; j++) if(f[t][j - 1] != inf) f[s][j] = min(f[s][j], f[t][j - 1] + tot * j);
}
}
}
int ans = inf;
for(int i = 0; i < n; i++) ans = min(ans, f[(1 << n) - 1][i]);
cout << ans << "\n";
return 0;
}
转载于:https://www.cnblogs.com/luoyibujue/p/10510698.html
