宝藏

GitHub跳转原题关系图返回列表

挖遍所有宝藏屋的最小开发代价：枚举生成树的根分层结构，状压 DP f[S] 表示已开发集合的最小代价，预处理子集连接边权和加速转移，O(3^n·n)。

OJ: roj

题目 ID: 3652

难度:省选/NOI-

标签:DP状压DP状态压缩NOIP

创建: 2026-10-02 13:20

更新: 2026-10-02 13:42

目录

  1. 形式化题目
  2. 正解
    1. 思路
      1. 代码
      2. 复杂度
    2. 总结

    形式化题目

    nn 个宝藏屋（n≤12n\le 12）、mm 条带权道路。从地面打通到某个宝藏屋代价巨大，而宝藏屋之间开发道路相对便宜；实际模型：选一个根（打通代价 0，按题面给定的「深度系数」加权），再开发若干道路使所有屋连通，最小化总代价（代价 = 每条开发道路的长度 × 所在层的深度系数，按题面约定求和）。

    正解

    思路

    1. 枚举根 + 分层结构 DP

    答案对应的连通结构是一棵以某屋为根的树。固定根 rr，按 BFS 分层，深度系数 dkd_k 已知。状态 SS = 已开发的屋集合：

    f[S]=min⁡T⊂S, T 可挂到 S∖T(f[S∖T]+d层⋅w(T,S∖T))f[S] = \min_{T \subset S,\ T \text{ 可挂到 } S\setminus T} \bigl(f[S\setminus T] + d_{\text{层}} \cdot w(T, S\setminus T)\bigr)

    其中 w(T,U)w(T,U) = TT 中每个点连到 UU 的最短边权和（每个点独立选最短边）。

    2. 预处理加速

    • mnd[S][v]：vv 与集合 SS 的最短边（去低位增量合并，O(2nn)O(2^n n)）；
    • extend[S]：枚举 SS 的子集 TT 并求连接权和，总工作量 O(3nn)O(3^n n)。

    对每个根跑 DP 取最小，n≤12n\le 12 时限内可行（根可以只枚举每个连通分量代表以加速）。

    代码

    Python 版：

    python
    #!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

INF = 10 ** 18


def solve() -> None:
    it = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(it), next(it)
    size = 1 << n

    g = [[INF] * n for _ in range(n)]  # g[u][v]：u,v 之间最短边长（重边取 min）
    for _ in range(m):
        u, v, w = next(it) - 1, next(it) - 1, next(it)
        if w < g[u][v]:
            g[u][v] = g[v][u] = w

    # mnd[S][v]：v 与已挖集合 S 之间最短一条边的长度（去掉 S 最低位后增量合并）
    mnd = [[INF] * n for _ in range(size)]
    for S in range(1, size):
        low = S & -S
        row_g, prev, row = g[low.bit_length() - 1], mnd[S ^ low], mnd[S]
        for v in range(n):
            wv, pv = row_g[v], prev[v]
            row[v] = wv if wv < pv else pv

    # 扩展表 extend[S] = [(T, wsum)]：T 是 S 的非空子集，且 T 中每个点都与
    # S\T 之间有边；wsum = 这些最短连接边的长度和（与挂在第几层无关）。
    # 直接按定义计算：内层枚举 T 的每一位累加 mnd，总工作量约 n·3^n。
    extend: list[list[tuple[int, int]]] = [[] for _ in range(size)]
    for S in range(1, size):
        wd: dict[int, int] = {}
        T = (S - 1) & S  # 从 S 的最大真子集开始降序枚举全部非空子集
        while T:
            total, ok, tt = 0, True, T
            row = mnd[S ^ T]  # T 中每个点都要接回 S\T
            while tt:
                v = (tt & -tt).bit_length() - 1
                wv = row[v]
                if wv == INF:  # 这个点接不回去，整个 T 非法
                    ok = False
                    break
                total += wv
                tt &= tt - 1
            if ok:
                wd[T] = total
            T = (T - 1) & S
        extend[S] = list(wd.items())

    full = size - 1
    masks_with = [[S for S in range(1, size) if S >> r & 1] for r in range(n)]

    ans = INF
    for r in range(n):  # 枚举赞助商免费打通、作为挖掘树根的宝藏屋
        dp_prev = [INF] * size  # dp[S]：挖开集合 S 的最小总代价（层数 ≤ 当前层）
        dp_prev[1 << r] = 0
        for k in range(2, n + 1):  # 第 k 层的新点都挂在第 k-1 层的点下
            dp_cur = dp_prev[:]  # 「最多 k 层」包含「更少层」的方案
            for S in masks_with[r]:
                new = dp_cur[S]
                for T, wsum in extend[S]:
                    if T >> r & 1:  # 新挖的点集不能包含早已免费打通的根
                        continue
                    base = dp_prev[S ^ T]
                    if base == INF:
                        continue
                    cost = base + wsum * (k - 1)  # 每条边的代价 = 边长 × 父结点深度
                    if cost < new:
                        new = cost
                dp_cur[S] = new
            if dp_cur == dp_prev:  # 这一层没有任何改进，更深的层也不会再有
                break
            dp_prev = dp_cur
        if dp_prev[full] < ans:
            ans = dp_prev[full]

    print(ans)


if __name__ == "__main__":
    solve()

    C++ 版（同一算法）：

    cpp
    /**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 13:14
 * update_at: 2026-10-02 13:14
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int a[maxn];

void read_data(){

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();
    
    return 0;
}

    复杂度

    • 时间复杂度：O(3n⋅n)O(3^n \cdot n)（预处理）+ O(2n⋅2n)O(2^n \cdot 2^n) 转移量级，n≤12n\le 12 可过。
    • 空间复杂度：O(2n⋅n)O(2^n \cdot n)。

    总结

    • 「选根 + 分层开发」的最小代价 = 枚举根的子集划分 DP。
    • 子集枚举总量 3n3^n 是此类题的标准规模，预处理 mnd/extend 把转移摊薄。
    • n≤12n\le 12 是状压 DP 的典型信号。