洛谷3959 [NOIP2017]宝藏

题目大意

给你$n$个点,$m$条边,要你选一个点作为根建一棵生成树满足代价最小

一棵生成树的代价是$\Sigma \; dep[i] * dis[fa_i][i]$, 其中$dep_i$表示$i$节点在这棵生成树中的深度(根节点深度为$0$,$dis[fa_i][i]$表示$i$节点到他父亲节点的距离

题目解析

首先通过$n\leq12$可以发现这是一道状压dp/搜索题

这里我们考虑状压dp

我们设状态$f[i]$表示选点的状态为$i$时,这棵生成树的最小代价,$st_{i,j}$表示当选点状态为$i$且$i$状态取最优方案时节点$j$的深度

那么我们可以很快想到一个dp方程

$$
f_{i|2^k}=\min{f_{i|2^k}, f_i+(g[j][k]*(st[i][j]+1))}, st_{i|2^k, k}=st_{i,j}+1(j \in i \;\mathrm{and}\;k \notin i)\
$$

初始值满足$f_{2^s}=0,st_{2^s,s}=0$,其余位置的$f$和$st$都为$\mathrm{inf}$

这个方程的复杂度是$O(n^2 \times 2^n)$的

注意到根不是固定的, 所以我们可以每次选定一个根来进行dp的计算,总复杂度$O(n^3\times2^n)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 13;
int n, m;
int g[MaxN][MaxN], st[1 << MaxN][MaxN], f[1 << MaxN];

int dp(int s)
{
memset(st, 0x3f, sizeof(st)), memset(f, 0x3f, sizeof(f));
int lim = (1 << n);
f[1 << s] = 0, st[1 << s][s] = 0;
for (int i = 1; i < lim; i++)
{
if (f[i] < 0x3f3f3f3f)
{
for (int j = 0; j < n; j++)
{
if (i & (1 << j))
{
for (int k = 0; k < n; k++)
{
if (!(i & (1 << k)))
{
if ((g[j][k] != 0x3f3f3f3f) && (f[i | (1 << k)] > f[i] + (g[j][k] * (st[i][j] + 1))))
{
f[i | (1 << k)] = f[i] + (g[j][k] * (st[i][j] + 1));
memcpy(st[i | (1 << k)], st[i], sizeof(st[i | (1 << k)]));
st[i | (1 << k)][k] = st[i][j] + 1;
}
}
}
}
}
}
}
return f[lim - 1];
}

int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof(g));
for (int i = 1; i <= m; i++)
{
int u, v, d;
scanf("%d%d%d", &u, &v, &d), --u, --v;
g[u][v] = std::min(g[u][v], d), g[v][u] = std::min(g[v][u], d);
}
int ans = 0x3f3f3f3f;
for (int i = 0; i < n; i++)
ans = std::min(ans, dp(i));
printf("%d\n", ans);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×