按挖掘深度分层做子集 DP，预处理新节点连接已挖集合的最短边代价。
OJ: luogu
题目 ID: P3959
难度:提高+/省选-
标签:状态压缩DP子集枚举分层python
日期: 2026-07-16 20:10
题意
任选一个根免费打通，其他点通过边接入。连接到深度 d-1 父点的边代价乘 d，求挖完所有点的最小总代价。
思路
dp[mask] 表示前若干层已经挖出 mask 的最小代价。第 depth 层选择补集的一个非空子集加入；每个新点连接到已挖集合中边权最小的点，贡献再乘当前深度。
先预处理 connection[v][mask]。对每个基础 mask，递归枚举补集子集并累计连接边权，所有基础集合的枚举总量是 2^n 子集的
所有单点根状态初值为 0，逐层滚动更新。
Python 知识
bit = mask & -mask和bit.bit_length()-1取得最低集合元素。- 闭包
enumerate_additions在枚举子集时同步累计费用，避免重复求和。 next_dp = dp[:]允许某一层不新增节点。
代码
python
import sys
INF = 10**18
data = iter(map(int, sys.stdin.buffer.read().split()))
n, edge_count = next(data), next(data)
edge = [[INF] * n for _ in range(n)]
for _ in range(edge_count):
u, v, weight = next(data) - 1, next(data) - 1, next(data)
edge[u][v] = edge[v][u] = min(edge[u][v], weight)
size = 1 << n
full = size - 1
connection = [[INF] * size for _ in range(n)]
for vertex in range(n):
for mask in range(1, size):
bit = mask & -mask
other = bit.bit_length() - 1
connection[vertex][mask] = min(connection[vertex][mask ^ bit], edge[vertex][other])
transitions = [[] for _ in range(size)]
for mask in range(1, size):
remaining_vertices = [vertex for vertex in range(n) if not mask >> vertex & 1]
def enumerate_additions(index, subset, cost):
if index == len(remaining_vertices):
if subset:
transitions[mask].append((mask | subset, cost))
return
enumerate_additions(index + 1, subset, cost)
vertex = remaining_vertices[index]
weight = connection[vertex][mask]
if weight < INF:
enumerate_additions(index + 1, subset | 1 << vertex, cost + weight)
enumerate_additions(0, 0, 0)
dp = [INF] * size
for root in range(n):
dp[1 << root] = 0
for depth in range(1, n):
next_dp = dp[:]
for mask, base in enumerate(dp):
if base == INF:
continue
for next_mask, cost in transitions[mask]:
next_dp[next_mask] = min(next_dp[next_mask], base + depth * cost)
dp = next_dp
print(dp[full])复杂度
预处理
总结
边费用乘树深度提示“按层加入节点”；n=12 则提示用集合表示已挖状态。
