BZOJ 3590 [SNOI 2013] Quare

这和Tarjan有什么关系?为什么在Tarjan专题?

思路:

选出无向图中包含所有点的权值和最小的双连通子图。

完全没思路,看了题解才会。。。。。

首先有一条重要的性质:一个双连通图可以拆成一个小双连通图和一条链。

我们首先能想到状压,用集合S表示点集。

那么设f[S]表示点集S构成的双连通图的最小权值和。

此题最大的思维难点来力:再预处理出两个数组g[S][i][j], h[S][i][1/0].

其中数组g表示以i、j为链端点,链的点集为S,这条链的最小权值。数组h表示从点i到点集S的最短边和次短边。

我们为什么要求这两个数组?由上文性质可以想到状态的转移,一个点集S是从一个更小的点集T和一条链转移来的。而这条链汇入点集T时有两种情况:1.链只有一个点。那么链与T的两条连边就是这个点到T的最小边和次小边。2.链不止一个点,那么连边就是两个端点与T的最小边。

我还没写过这么长的状压DP。。。。。


代码:

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
#include <bits/stdc++.h>

int mx, n, m, t, ecnt, head[15], f[1 << 13], g[1 << 13][13][13], h[1 << 13][13][3], bin[13], cnt[1 << 13];
struct Edge {int to, nxt, val;} e[233333];

inline void AddEdge(int f, int to, int val) {
e[++ecnt] = {to, head[f], val}, head[f] = ecnt;
}

signed main() {
scanf("%d", &t);
for (int i = 1; i < 13; i++) bin[i] = (1 << (i - 1));
for (int i = 1; i < (1 << 13); i++) cnt[i] = cnt[i >> 1] + (i & 1);
while (t--) {
memset(g, 0x10, sizeof(g));
memset(h, 0x10, sizeof(h));
memset(f, 0x10, sizeof(f));
memset(head, 0, sizeof(head));
scanf("%d%d", &n, &m);
mx = (1 << n) - 1;
for (int i = 1, x, y, z; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
AddEdge(x, y, z), AddEdge(y, x, z);
}
for (int i = 1; i <= n; i++)
g[bin[i]][i][i] = 0;
for (int x = 1; x <= n; x++)
for (int i = head[x], y = e[i].to; i; i = e[i].nxt, y = e[i].to)
g[bin[x] | bin[y]][x][y] = std::min(g[bin[x] | bin[y]][x][y], e[i].val);
for (int S = 1; S <= mx; S++)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if ((bin[x] & S) && (bin[y] & S))
for (int i = head[y], z = e[i].to; i; i = e[i].nxt, z = e[i].to)
if (!(bin[z] & S))
g[S | bin[z]][x][z] = std::min(g[S | bin[z]][x][z], g[S][x][y] + e[i].val);
for (int S = 1; S <= mx; S++)
for (int x = 1; x <= n; x++)
if (!(S & bin[x]))
for (int i = head[x], y = e[i].to; i; i = e[i].nxt, y = e[i].to)
if (S & bin[y]) {
if (e[i].val <= h[S][x][0])
h[S][x][1] = h[S][x][0], h[S][x][0] = e[i].val;
else if (e[i].val < h[S][x][1])
h[S][x][1] = e[i].val;
}
for (int i = 1; i <= n; i++) f[bin[i]] = 0;
for (int D = 1; D <= mx; D++)
if (cnt[D] >= 2)
for (int S = (D - 1) & D, T = D - S; S; S = (S - 1) & D, T = D - S)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if ((S & bin[x]) && (S & bin[y])) {
if (x == y)
f[D] = std::min(f[D], f[T] + g[S][x][x] + h[T][x][0] + h[T][x][1]);
else
f[D] = std::min(f[D], f[T] + g[S][x][y] + h[T][x][0] + h[T][y][0]);
}
if (f[mx] >= 0x10101010)
puts("impossible");
else printf("%d\n", f[mx]);
}
return 0;
}

评论

Your browser is out-of-date!

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

×