抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

题意

n 个点组成的图,可以选择一个点作为出发点,试找到一个生成树使得总代价最小。每加一条边产生的代价为起始点到边的一段的点的个数乘上边长

n\le 12

题解

这里是 O(3^nn) 的状压做法。分析这道题:很重要的一点就是代价是和树高息息相关的。所以有一些做法肯定是不行的。然后考虑这样子进行 dp: f_{S, l} 表示状态为 S ,树高为 l 的最小代价。然后每次转移的时候枚举 S 的子集 S' ,用 f_{S',l - 1} 转移 f_{S, l}

转移的计算:令 g_{s_1, S_2} 表示从状态 S_1 到状态 S_2 (其中 S_1\subset S_2 )的最小边长总和。很明显这个东西是可以提前计算的,于是转移方程就来了:

f_{S, l} = \min_{S'\subset S}\{f_{S', l - 1} + g_{S', S}\times l\}

至于 g_{S_1, S_2} 的计算, O(2^n) 枚举 S_2 ,然后枚举 S_2 的子集 S_1 但是此时需要保证枚举顺序倒序的。就是若 S_1\subset S_1' ,则 S_1' 必须比 S_1 先枚举到因为这样就可以只考虑单条边的加入。这一部分代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
FOR(i, 1, (1 << n) - 1)
{
int v = 0;
for (int s = ((1 << n) - 1) ^ i, j = s; j; j = (j - 1) & s)//枚举 i 的子集然后倒序记录
nxt[j] = v, v = j;
for (int j = v; j; j = nxt[j])//从最小的集合开始枚举
{
int x = lg[j & -j] + 1, v = 3e6 + 5;//提出 j 内的最后一个点 x
FOR(y, 1, n)
if ((1 << (y - 1)) & i) v = min(v, e[x][y]);//考虑在 i 内的一个点 y,且 y 能与 x 相连
g[i][j] = g[i][j ^ (j & -j)] + v;//这就是为什么要从小枚举。小的要贡献给大的
}
}

同时这里有一个枚举 i 的子集的方法:for (int j = i; j; j = (j - 1) & i)。原理比较的妙不可言。

总的代码就出来了:

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
59
60
61
#include <cstdio>
#include <cctype>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)

const int maxn = 13, maxm = 1e3 + 5;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

inline int min(int a, int b) {return a < b ? a : b;}

int e[maxn][maxn], n;
int g[1 << maxn][1 << maxn], f[1 << maxn][maxn], nxt[1 << maxn], lg[1 << maxn];

int main()
{
memset(e, 0x3f, sizeof e), memset(f, 0x3f, sizeof f);
n = read();
FOR(i, 1, n - 1) lg[1 << i] = i;
int m = read();
while (m--)
{
int u = read(), v = read(), w = read();
if (e[u][v] > w) e[u][v] = e[v][u] = w;
}


FOR(i, 1, (1 << n) - 1)
{
int v = 0;
for (int s = ((1 << n) - 1) ^ i, j = s; j; j = (j - 1) & s)
nxt[j] = v, v = j;
for (int j = v; j; j = nxt[j])
{
int x = lg[j & -j] + 1, v = 3e6 + 5;
FOR(y, 1, n)
if ((1 << (y - 1)) & i) v = min(v, e[x][y]);
g[i][j] = g[i][j ^ (j & -j)] + v;
}
}

FOR(i, 1, n) f[1 << (i - 1)][0] = 0;
FOR(l, 1, n - 1)
FOR(i, 1, (1 << n) - 1)
for (int j = i; j; j = (j - 1) & i)
f[i][l] = min(f[i][l], f[i ^ j][l - 1] + g[i ^ j][j] * l);
int ans = 0x3f3f3f3f;
FOR(l, 0, n) ans = min(ans, f[(1 << n) - 1][l]);
printf("%d\n", ans);
return 0;
}

评论




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme