宝藏
题目背景：
NOIP2017 D2T2
分析：状压DP
个人感觉，是这一次NOIP最难的一道题了，虽然拿到第一反应就知道是状压DP，但是实际上想了一个多小时也没有什么头绪。首先考虑，定义f[i][mask]表示，当前最深深度为i，已经在树上的结点的状态为mask，我们只需要枚举，这一次新加入哪些结点，接在最后一层，为什么只用接在最后一层，考虑，如果存在一个结点，接在i以上的一层更优，那么在转移当时的状态时，就肯定有做过将这个节点接上的操作，那么那个状态一定已经存在，所以不会影响最后的答案。那么每一次转移，就只需要枚举，不在mask中的结点的接入情况，需要求取这些结点，到集合中结点的边权的最小值就可以了。复杂度为O(n * 3n + n3 * 2n)
Source：
/*created by scarlyw
*/
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <set>
#include <queue>template<class T>
inline void R(T &x) {static char c;static bool iosig;for (c = getchar(), iosig = false; !isdigit(c); c = getchar())if (c == '-') iosig = true; for (x = 0; isdigit(c); c = getchar()) x = ((x << 2) + x << 1) + (c ^ '0');if (iosig) x = -x;
}const int MAXN = 12 + 3;
const int MAXX = 12;
const int INF = 100000000;int f[MAXN][1 << MAXX | 1], map[MAXN][MAXN];
int total, ans, cur_dep, cur_s, n, m, x, y, v;struct node {int to, w;node(int to = 0, int w = 0) : to(to), w(w) {}inline bool operator < (const node &a) const {return w < a.w;}
} ;std::vector<node> edge[MAXN];inline void read_in() {R(n), R(m), total = (1 << n) - 1;for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) map[i][j] = INF;for (int i = 1; i <= m; ++i) {R(x), R(y), R(v), x--, y--;map[x][y] = std::min(map[x][y], v), map[y][x] = std::min(map[y][x], v);}for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)if (map[i][j] != INF) edge[i].push_back(node(j, map[i][j]));for (int i = 0; i < n; ++i) std::sort(edge[i].begin(), edge[i].end());
}std::vector<node> q;inline void dfs(int cur, int sum, int stats) {if (cur == q.size()) {f[cur_dep][cur_s | stats] = std::min(f[cur_dep][cur_s | stats], f[cur_dep - 1][cur_s] + sum * cur_dep);return ;}dfs(cur + 1, sum + q[cur].w, stats | (1 << q[cur].to));dfs(cur + 1, sum, stats);
}inline void solve() {memset(f, 127, sizeof(f));for (int i = 0; i < n; ++i) f[0][1 << i] = 0;for (int dep = 1; dep < n; ++dep) {for (int s = 1; s < total; ++s) {if (f[dep - 1][s] >= INF) continue ;q.clear();for (int cur = 0; cur < n; ++cur) {if (s & (1 << cur)) continue ;for (int p = 0; p < edge[cur].size(); ++p) {node *e = &edge[cur][p];if (s & (1 << e->to)) {q.push_back(node(cur, e->w));break ;}}}cur_dep = dep, cur_s = s, dfs(0, 0, 0);}}ans = INF;for (int i = 0; i < n; ++i) ans = std::min(ans, f[i][total]);std::cout << ans;
}int main() {read_in();solve();return 0;
}