[NOIP2017] 宝藏

it2022-05-06  0

/* 宝藏的子集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


最新回复(0)