彻底搞懂状压 DP：NOIP 2017《宝藏》重构题解

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1

4

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2

5

// 预处理 min_cost 数组
// 枚举所有可能的已选集合 S
for (int S = 1; S < (1 << n); ++S) {
    // 枚举不在集合 S 中的节点 i
    for (int i = 0; i < n; ++i) {
        if ((S & (1 << i)) == 0) { // i 不在 S 中
            int mn = INF;
            // 找 S 中距离 i 最近的节点 j
            for (int j = 0; j < n; ++j) {
                if (S & (1 << j)) {
                    mn = min(mn, adj[j][i]);
                }
            }
            min_cost[S][i] = mn; // 记录最小距离
        }
    }
}

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const long long INF = 0x3f3f3f3f3f3f3f3fLL; // 使用 long long 级别的无穷大
int n, m;
long long adj[15][15];             // 邻接矩阵，存两点间最短边
long long min_cost[1 << 12][15];   // min_cost[S][u] 表示点 u 到集合 S 的最小边权
long long dp[15][1 << 12];         // dp[树深度][点集]

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 1. 初始化与读入
    if (!(cin >> n >> m)) return 0;
  
    memset(adj, 0x3f, sizeof(adj));
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        u--; v--; // 转换为 0-based 索引，方便位运算
        // 处理重边，保留最小的
        adj[u][v] = min(adj[u][v], w);
        adj[v][u] = min(adj[v][u], w);
    }

    // 2. 预处理 min_cost 数组 (空间换时间)
    int max_state = (1 << n);
    for (int S = 1; S < max_state; ++S) {
        for (int i = 0; i < n; ++i) {
            if ((S & (1 << i)) == 0) { // i 不在集合 S 中
                long long mn = INF;
                for (int j = 0; j < n; ++j) {
                    if (S & (1 << j)) { // j 在集合 S 中
                        mn = min(mn, adj[j][i]);
                    }
                }
                min_cost[S][i] = mn;
            }
        }
    }

    // 3. DP 初始化
    memset(dp, 0x3f, sizeof(dp));
    // 深度为 0 的时候，树里只能有一个点（作为根节点），代价为 0
    for (int i = 0; i < n; ++i) {
        dp[0][1 << i] = 0;
    }

    // 4. 开始 DP
    // 枚举树的最大深度 i (最多为 n-1 层)
    for (int i = 1; i < n; ++i) {
        // 枚举当前所有的节点集合 S
        for (int S = 1; S < max_state; ++S) {
        
            // 枚举 S 的所有子集 sub_S (代表上一层及以前已经建好的集合)
            // 这种枚举方式可以正好遍历 S 的所有真子集
            for (int sub_S = S; sub_S > 0; sub_S = (sub_S - 1) & S) {
                if (sub_S == S) continue; // 上一层的集合不能是 S 本身，必须有新点加入
            
                // 上一层状态都达不到，直接跳过
                if (dp[i - 1][sub_S] == INF) continue; 

                long long current_expand_cost = 0;
                bool is_valid = true;
            
                // 找出这一次扩展加入的新点：diff = S 剔除 sub_S
                int diff = S ^ sub_S; 
            
                // 遍历每一个新加入的点 u
                for (int u = 0; u < n; ++u) {
                    if (diff & (1 << u)) {
                        // 寻找 u 连接到旧集合 sub_S 的最小代价
                        if (min_cost[sub_S][u] == INF) {
                            is_valid = false; // 原图根本不连通，无法扩展
                            break;
                        }
                        // 累加代价：边权 * 当前深度 i
                        current_expand_cost += min_cost[sub_S][u] * i;
                    }
                }

                // 如果转移合法，松弛更新 dp 值
                if (is_valid) {
                    dp[i][S] = min(dp[i][S], dp[i - 1][sub_S] + current_expand_cost);
                }
            }
        }
    }

    // 5. 统计答案
    long long ans = INF;
    // 最终包含所有点 (即状态 (1<<n)-1)，它可能在任意深度 0 到 n-1 完成
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dp[i][max_state - 1]);
    }

    cout << ans << "\n";
    return 0;
}