最小生成树【最小瓶颈路、斯坦纳树、最小树形图、最小乘积生成树】Summary
知识点总结
最小瓶颈路
在最小生成树的基础上倍增处理下边权最大值就行
斯坦纳树
就是一个状压dp: 表示以i为根，指定集合中的点的连通状态为state的生成树的最小总权值 转移方程有两种： 1、枚举子集： 枚举子集的方法：
1 | for(sub=(state-1)&state;sub;sub=(sub-1)&state) |
2、松弛操作（i到j有边相连）
最小树形图
最小乘积生成树(这篇有图，比较清晰)
Problems
Codeforces 733F Drivers Dissatisfaction(最小生成树+LCA)
Codeforces 733F Drivers Dissatisfaction(最小生成树+LCA)
BZOJ3732 Network(最小瓶颈路)
最小瓶颈路模板
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
using namespace std;
const int Maxn = 150000 + 10, Maxm = 600000 + 100;
struct node
{
int x, y, z;
}A[Maxn];
inline int cmp (node a, node b)
{
return a.z < b.z;
}
int N, M;
int e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm];
int anc[Maxn][21], Max[Maxn][21];
int fa[Maxn], deep[Maxn];
inline void add_edge (int x, int y, int z)
{
To[++e] = y;
Next[e] = Begin[x];
Begin[x] = e;
W[e] = z;
}
inline int find (int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void dfs (int x)
{
for (int i = 1; i <= 20; ++i) anc[x][i] = anc[anc[x][i - 1]][i - 1], Max[x][i] = max(Max[x][i - 1], Max[anc[x][i - 1]][i - 1]);
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == anc[x][0]) continue;
anc[y][0] = x;
Max[y][0] = W[i];
deep[y] = deep[x] + 1;
dfs(y);
}
}
inline int Lca (int x, int y)
{
int Ans = 0;
if (deep[x] < deep[y]) swap(x, y);
for (int i = 20; i >= 0; --i)
if (deep[anc[x][i]] >= deep[y])
Ans = max(Ans, Max[x][i]), x = anc[x][i];
if (x == y) return Ans;
for (int i = 20; i >= 0; --i)
if (anc[x][i] != anc[y][i])
Ans = max(Ans, max(Max[x][i], Max[y][i])), x = anc[x][i], y = anc[y][i];
Ans = max(Ans, max(Max[x][0], Max[y][0]));
return Ans;
}
int main()
{
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
int K;
scanf("%d%d%d", &N, &M, &K);
for (int i = 1; i <= N; ++i) fa[i] = i;
for (int i = 1; i <= M; ++i)
scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].z);
sort(A + 1, A + M + 1, cmp);
int cnt = 0;
for (int i = 1; i <= M; ++i)
{
int fx = find(A[i].x), fy = find(A[i].y);
if (fx == fy) continue;
add_edge (A[i].x, A[i].y, A[i].z);
add_edge (A[i].y, A[i].x, A[i].z);
// add_edge (fx, fy, A[i].z);
// add_edge (fy, fx, A[i].z);
fa[fy] = fx;
++cnt;
if (cnt == N - 1) break;
}
dfs(1);
while (K--)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", Lca(x, y));
}
return 0;
}
Hdu3311 Dig the Wells（斯坦纳树+状压dp+SPFA）
Hdu3311 Dig the Wells（斯坦纳树+状压dp+SPFA）
Hdu4085 Peach Blossom Spring(斯坦纳树)
Hdu4085 Peach Blossom Spring(斯坦纳树)