abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S5442 【荒诞】

发表于

Dsceription

一个 $n$ 个点，$m$ 条边的无向图，在第 $i$ 个点建立一个旅游站点的费用是 $c_i$。特别地，这张图中的任意两点间不存在节点数超过 $10$ 的简单路径。
现在要建造一些旅游站点，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。试求出总花费的最小值。

单个测试点的时间限制为 3s。

Solution

读题，观察到任意两点间不存在节点数超过 $10$ 的简单路径。

容易发现每个连通块对答案的影响是独立的，于是对于每个连通块分开做。

考虑对于每个连通块建出 DFS 树，显然它只存在返祖边。

考虑状压 DP，设 $f_{i, S}$ 表示当前从点 $i$ 到根节点的路径上的点的覆盖状态为 $S$ 的情况下的最小华为。

其中 S 是一个三进制状态，0 表示未选且当前未被覆盖，1 表示未选但当前已被覆盖，2 表示选了。

然后按照 DFS 序进行状压 DP 即可，注意要考虑返祖边对转移的干扰。

Code

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <cstring>
#define maxN 50010
struct Edge{ int x, y, g; } b[maxN << 1];
int inf = 0, len = 0, n = 0, m = 0;
int val[maxN];
int pow[20], fa[20];
int dep[maxN], h[maxN];
int f[2][60010];
int min (int x, int y)
{
	return x < y ? x : y;
}
void ins (int x, int y)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].g = h[x];
	h[x] = len;
}
void dfs (int x)
{
	int T = dep[x] & 1;
	memset(f[T], 127 / 3, sizeof(f[T]));
	memset(fa, 0, sizeof(fa));
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(dep[y] && dep[y] < dep[x])
		{
			fa[dep[y]] = 1;
		}
	}
	const int maxS = pow[dep[x]] - 1;
	for(int S = 0;S <= maxS; S++)
	{
		if(f[1 - T][S] != inf)
		{
			bool flag = false;
			int SS = S + (pow[dep[x]] << 1);
			for(int i = 1;i < dep[x]; i++)
			{
				if(fa[i])
				{
					if(!((SS / pow[i]) % 3))
					{
						SS += pow[i];
					}
					if((S / pow[i]) % 3 == 2)
					{
						flag = true;
					}
				}
			}
			f[T][SS] = min(f[T][SS], f[1 - T][S] + val[x]);
			if(flag)
			{
				f[T][S + pow[dep[x]]] = min(f[T][S + pow[dep[x]]], f[1 - T][S]);
			}
			else
			{
				f[T][S] = min(f[T][S], f[1 - T][S]);
			}
		}
	}
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(!dep[y])
		{
			dep[y] = dep[x] + 1;
			dfs(y);
			for(int S = 0;S < pow[dep[y]]; S++)
			{
				f[T][S] = min(f[1 - T][S + pow[dep[y]]], f[1 - T][S + (pow[dep[y]] << 1)]);
			}
		}
	}
}
int main ()
{
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= n; i++)
	{
		scanf("%d", &val[i]);
	}
	for(int i = 1;i <= m; i++)
	{
		int x = 0, y = 0;
		scanf("%d %d", &x, &y);
		ins(x, y), ins(y, x);
	}
	pow[1] = 1;
	for(int i = 2;i < 20; i++)
	{
		pow[i] = pow[i - 1] * 3;
	}
	int Ans = 0;
	for(int root = 1;root <= n; root++)
	{
		if(!dep[root])
		{
			memset(f, 127 / 3, sizeof(f));
			inf = f[0][0];
			f[0][0] = 0;
			dep[root] = 1;
			dfs(root);
			Ans += min(f[1][1], f[1][2]);
		}
	}
	printf("%d", Ans);
	return 0;
}