P3959 宝藏

题目名称

问题

P3959 宝藏
在一个带权无向图中任选一个宝藏屋作为起点，并逐步开发道路，使所有宝藏屋都能够从起点到达。开发一条道路的费用与道路长度以及它所在的层数有关，求最小总代价。

数据规模：$n \le 12$，$m \le 1000$。

问题抽象

我最开始注意到，起点是可以任意选择的，而且某一条道路的费用不仅与边权有关，还与它距离起点的层数有关，因此首先想到的是枚举根节点，再进行某种状压DP。

然后我发现，最终开发出来的道路必定形成一棵树，由于道路长度都是正的，如果方案中出现了换，那么删掉某条冗余道路后，所有宝藏仍然连通，总代价还会减小，因此最优方案中一定不存在环，也就是说，最终选择的道路一定构成一棵以起点为根的生成树。

若把根节点的深度记为 $0$，那么一个位于第 $d$ 层的节点，通过父边接入生成树的时候，就需要支付 $d \times w(u, v)$。

由此我们抽象出了本题的形式化问题：在一个 $n \le 12$ 的带权无向图中，任选根节点并构造一棵有根生成树，使每条父边的边权乘以子节点深度后的总和最小。

关键思路

观察到数据规模只有 $n \le 12$，因此可以用一个二进制状态 mask 来表示已经挖掘的宝藏屋集合。但是我们发现只记录 mask 是不充分的，同一个已挖的集合，在不同的层数中，未来的决策并不是等价的。

所以我们还需要额外记录当前扩展到了第几层，定义 $f[d][mask]$ 表示已经挖掘了 mask 中的宝藏屋，下一层为 $d$，能取到的最小代价。

由于起点可以任选，所以初始化所有单点集合：$f[1][1 \ll r] = 0$。

接下来，我们设 mask 为已经挖掘的节点，rem = all ^ mask 表示尚未挖掘的节点，sub 表示本轮加入的下一批节点。

然后就是转移了；对于每个新节点 $v \in sub$，它只需要从以挖掘的节点选择一条最便宜的道路接入。记 $\displaystyle mn[mask][v]=\min_{u\in mask}w(u,v)$，那么本轮加入 sub 的费用为 $\displaystyle d\sum_{v\in sub}mn[mask][v]$。

$$f[d+1][mask\cup sub] = \min\left( f[d+1][mask\cup sub], f[d][mask] + d\sum_{v\in sub}mn[mask][v] \right)$$

不过这里可能还有一个疑惑？看起来允许新节点连接到 mask 中任意一个更早出现的点，而不只连接上一层，不过这是没关系的。

如果一个节点选择的父节点早已出现，那么把这个节点提前到父节点的下一层，只会减少它以及后续节点的费用，不会破坏连通性。因此一定存在一种最优方案，使得每个节点都在父节点之后尽早加入。

于是我们按批枚举下一层，不会漏掉这种最优生成树。

摘要

本题的状态不是一条具体的路径，而是已经完成的分层构造状态。
当未来费用同时依赖 “已经选择了什么” 和 “当前进行到哪个阶段”，状态中必须同时保存这些信息。

这里还有一个小 Trick，在枚举 rem 的所有非空子集时，我们可以采用：

for( int sub = rem; sub; sub = ( sub - 1 ) & rem )

复杂度为 $\mathcal{O}(3^{n})$，因为每个点都有三种状态，在 mask 中，在 rem 中，都不在。

实现

• 时间复杂度：$O(n^2 3^n)$；

• 空间复杂度：$O(n2^n)$；

▶

代码

const int maxn = 12 + 5;
const int maxs = (1 << 12) + 5;
const int mod = 998244353;

ll read( ) { /* 模板代码略 */ }

ll mat[maxn][maxn];
ll f[maxn][maxs];

void solve( ) {
    int n = read( ), m = read( );
    int N = 1 << n;

    for( int i = 0; i < n; ++ i ) {
        for( int j = 0; j < n; ++ j ) {
            mat[i][j] = i == j ? 0 : inf;
        }
    }
    
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ) - 1, v = read( ) - 1;
        ll w = read( );
        mat[u][v] = min( mat[u][v], w );
        mat[v][u] = min( mat[v][u], w );
    }

    for( int d = 1; d <= n; ++ d ) {
        for( int mask = 0; mask < N; ++ mask ) {
            f[d][mask] = inf;
        }
    }

    for( int i = 0; i < n; ++ i ) {
        f[1][1 << i] = 0;
    }

    for( int d = 1; d < n; ++ d ) {
        for( int mask = 1; mask < N; ++ mask ) {
            if( f[d][mask] == inf ) continue;

            int rem = (N - 1) ^ mask;

            for( int sub = rem; sub; sub = (sub - 1) & rem ) {
                ll cost = 0;
                bool ok = 1;
                for( int v = 0; v < n; ++ v ) {
                    if( !( sub & (1 << v) ) ) continue;
                    ll res = inf;
                    for( int u = 0; u < n; ++ u ) {
                        if( !( mask & (1 << u ) ) ) continue;
                        res = min( res, mat[u][v] );
                    }
                    if( res == inf ) {
                        ok = 0;
                        break;
                    }
                    cost += res;
                }
                if( ok == 0 ) continue;
                int nxt = mask | sub;
                f[d + 1][nxt] = min( f[d+1][nxt], f[d][mask] + 1ll * d * cost );
            }
        }
    }

    ll ans = inf;
    for( int d = 1; d <= n; ++ d ) {
        ans = min( ans, f[d][N - 1] );
    }
    cout << ans << '\n';
}