python/TangDou/AcWing/StateCompression/529_DP.cpp

#include <bits/stdc++.h>
using namespace std;

/*
状压DP的二进制表示法,状态压缩DP有两个性质：
1、它说多大就设置多大，不要再扩大设置，速度会慢。
2、一般状态压缩DP数组下标从0开始
*/
const int N = 12;           // 节点个数上限
const int M = 1 << N;       // 节点的状态表示 2^N种状态
const int INF = 0x3f3f3f3f; // 正无穷

int g[N][N]; // 邻接矩阵，g[i][j]:i号点和j号点之间的距离

// 记录有效状态转移关系
int p[M]; // p[x]:状态x中的存在(指值为1)每一个数位i，通过g[i][j],可以连接到j1,j2,...等节点，最终可以到达的所有状态为p[x]
          // 比如i=00001->0号节点值为1，0号节点与1、3号节点之间有边，那么p[i]=p[00001]=01011

int n, m; // 节点数,边数
/* 递推关系：　f[S][j]=min(f[Spre][j-1]+cost)
  S：当前状态，Spre是指S的所有前序状态，
  也就是Spre通过引入某些合法边(当前状态某个位置有1，同时，由此处的1有相关的边。不是只有一条，是数位为1的所有节点都可以引入合法边)
  ，可以形成S这个状态。 由于引入边的不同，导致代价不一样，需要求代价的最小值
*/
int f[M][N];      // f[i][j]:所有二进制状态表示为i,且树高为j的生成树的集合，属性:最小代价
vector<int> v[N]; // i这个点，到哪些点有边

int main() {
    scanf("%d %d", &n, &m); // 节点数量和边数量

    // 1、地图初始化
    memset(g, 0x3f, sizeof g);               // 全部初始为正无穷,描述:所有节点之间均未连通
    for (int i = 0; i < n; i++) g[i][i] = 0; // 每个点到自己的距离为0

    // 2、读入边
    while (m--) {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);        // 起点，终点，权值
        a--, b--;                             // 状态压缩，习惯下标从0开始，题目给的节点号是从1开始的，需要统一处理减1
        g[a][b] = g[b][a] = min(g[a][b], w);  // 无向图 + 防止重边 + 留最小值
        v[a].push_back(b), v[b].push_back(a); // 记录下a可以到达哪些点,其实如果不这么记忆的话，那么就需要枚举每个点对着哪些点，因为数据量小，速度应该也挺快
    }

    /*
    3、预处理有效状态之间的转移关系 i->p[i]
    转移办法：标识为1的节点上通过枚举已知边,扩展为新状态p[i]
    */
    for (int i = 0; i < 1 << n; i++)                                        // 枚举每个状态
        for (int j = 0; j < n; j++)                                         // 枚举状态的每个位置
            if (i >> j & 1) {                                               // 如果当前位是1
                p[i] |= 1 << j;                                             // 原来的i状态中的1，扩展后还是有的
                for (int k = 0; k < v[j].size(); k++) p[i] |= 1 << v[j][k]; // 由j带来的扩展点有v[j].size()个
            }
    /*
    Q:问题：
    if (i >> j & 1) {
         p[i] |= 1 << j;
         for (int k = 0; k < v[j].size(); k++) p[i] |= 1 << v[j][k];
    }
    可以改写成：
    if (i >> j & 1) {
         p[i] += 1 << j;
         for (int k = 0; k < v[j].size(); k++) p[i] += 1 << v[j][k];
    } 吗？它们两个是等价的吗？

    答：它们并不是完全等价。
    这两个表达式都是将二进制数p[i]的第j位设置为1，但是p[i] |= 1 << j;相比p[i] += 1 << j;更加高效。
    这是因为使用位运算符OR(|=)可以避免临时变量和函数调用，并且可以利用位级别的并行性加快操作速度。而加法运算则需要进行进位，速度相对较慢。
    此外，p[i] += 1 << j; 如果第j位之前已经是1的话，会导致进位，此时p[i]的值会发生改变，而p[i] |= 1 << j; 不会改变已有的位。

    回到上面的代码中，如果我们没有写成 | 运算符，而是采用了+运算符，那么根据业务上的逻辑，p[i]的值可能首先被
         for (int k = 0; k < v[j].size(); k++) p[i] += 1 << v[j][k]; 进行填充，
         那么 j'=v[j][k],就会提前将对应的数值加到p[i]中去，而下次来到执行 p[i] +=1<<j 时，就会造成重复累加，结果错误。

    因此，在二进制位运算时，应尽量使用位运算符。
    */

    // 4、动态规划
    // 4.1 DP数组初始化
    memset(f, 0x3f, sizeof f);                    // 预求最小，先设最大
    for (int i = 0; i < n; i++) f[1 << i][0] = 0; // 赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道",选择打通哪一条都是一样的，都不要钱，所以在选择每一个节点为起点时，费用都是0

    // 4.2 状态转移
    for (int i = 0; i < 1 << n; i++) {               // 枚举每个状态i
        for (int j = i - 1; j; j = (j - 1) & i) {    // 枚举i状态的真子集j,只有真子集才有资格进行转移
            if ((p[j] & i) == i) {                   // 如果子状态j可以通过已知边，扩展为可以正好匹配i,才是真正可以转移的有效子状态
                int x = i ^ j;                       // x:j->i增加出来的元素，也就是状态差集,都是j里没有，i里有的数字位1
                int cost = 0;                        // cost记录在状态j到达状态i过程中用到的最小花费
                for (int k = 0; k < n; k++)          // 枚举x每一个节点k
                    if (x >> k & 1) {                // 找出x中数位是1的节点k
                        int t = INF;                 // t表示从j到i使得覆盖掉第k个点需要的最小代价
                        for (int u = 0; u < n; u++)  // 枚举j的每一个数位u
                            if (j >> u & 1)          // 如果此数位是1,有资格引边
                                t = min(t, g[u][k]); // 如果k点是通过u点连接过去的，那么带来的代价就是g[u][k]
                        cost += t;                   // 把x的所有元素都纳入的最小代价和
                    }

                /*
                 当前状态是i,前序状态是j,它们之间的差集是x, k为枚举x的每一个数字1位，为了点亮k点，最小代价是cost，
                 整体代价：cost*k(层数越深，挖掘成本系数越大)
                 迁移方式：加边(数位是1，并且，由此可以引出合法边。不只1条，可是多条。)

                 理解与感悟：
                 (1) 先有状态转移方程，再有填充顺序
                 (2) j->i 需要枚举有效状态转移关系
                 (3) k-1 -> k 就是层次增加了一层
                 (4) k∈[1,n) 是因为树根在0层，直线的话，最后一层是n-1
                 (5) 上面的都好办，关键在于这个 cost,这个东西需要枚举两个转移状态之间的对应关系，结合点与点之间的距离才能计算出来
                 最小的代价和，最小代价和 乘以 层数，才是真正的整体代价。
                */
                for (int k = 1; k < n; k++) f[i][k] = min(f[i][k], f[j][k - 1] + cost * k);
            }
        }
    }

    // 5、枚举答案, 最小值可能出现在任意一层
    int res = INF;
    for (int i = 0; i < n; i++)
        res = min(res, f[(1 << n) - 1][i]); //(1 << n) - 1表示全选状态，即111111...

    // 6、输出结果
    cout << res << endl;
    return 0;
}