次小生成树
介绍
次小生成树是就是第二小的生成树.其权值可能和最小生成树一样,也可能稍大于最小生成树.
另外还有严格最小生成树,就是指权值大于最小生成树的最小的生成树,以下先介绍非严格的.
算法
次小生成树有现有的模板,思路主要是魔改最小生成树的模板.基于Prim和Kruskal .
在求出最小生成树(以下简称mst)后,尝试将其他边加入,这样必然会生成环,去掉环中除新加边之外的最大的边,就能构建出新的生成树.然后遍历过所有边之后,取结果的最小值,就是次小生成树.
注:次小生成树和最小生成树只有一个边不一样是一个定理.
Prim版
分析
为了简化复杂度,我们就在Prim的过程中预处理出path[][] ,表示两点路径上的最大边的权值 ,pre[i]表示i通过哪个点接入最小生成树,used[i][j]表示i->j这条边是否存在,G[i][j]是邻接矩阵.
其中一个难点就是如何求path.
我们可以从结果倒推求法.我们发现如果新加一个边i->j,那么就需要看path[i][j],这个问题其实是可以分治的,就是我们只需要看path[i][pre[j]] 和 G[pre[j]][j]就可以了.
为什么呢?因为i到j的路径一定可以表示成i到pre[j]的路径和pre[j]到j的路径,然后最大值也一定是这两条路径中的最大值.而可以继续这样递推下去的.我们采用dp的思想优化这一步操作.
path[pos][j]=path[j][pos]=max(path[j][pre[pos]]*1ll,dis[pos]);
1
2
3
4
5
6
7
8
9
10
11
12
// path初始值为0
// i j 不连通时G[i][j]等于inf
for(int j=1; j<=n; ++j) {
if(vis[j]&&j!=pos) { // 如果j是树上一点,那么就更新path,这样是可以将path全部更新的
path[pos][j]=path[j][pos]=max(path[j][pre[pos]]*1ll,dis[pos]);
} else { // 如果j不在树上,就尝试更新pre和dis
if(!vis[j]&&dis[j]>G[j][pos]) {
dis[j]=G[j][pos];
pre[j]=pos;
}
}
}
模板
时空复杂度O(n^2)
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
int n,m;
struct NODE {
int v,w,nxt;
} edge[maxn];
int head[5100];
int pre[5100];
ll path[5100][5100];
bool used[5100][5100];
int G[5100][5100];
int cnt=1;
void add(int u,int v,int w) {
edge[cnt].w=w;
edge[cnt].v=v;
edge[cnt].nxt=head[u];
head[u]=cnt++;
}
ll dis[5100];
bool vis[5100];
ll Prim() {
ll ans=0;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
path[i][j]=0;
used[i][j]=0;
}
}
for(int i=1; i<=n; ++i) {
dis[i]=infll;
vis[i]=0;
}
for(int j=2; j<=n; ++j) {
dis[j]=G[1][j];
pre[j]=1;
}
dis[1]=0;
vis[1]=1;
pre[1]=1;
int pos=0;
for(int i=2; i<=n; ++i) {
ll minn=infll;
int minid=-1;
for(int j=1; j<=n; ++j) {
if(!vis[j]&&dis[j]<minn) {
minn=dis[j];
minid=j;
}
}
if(minid==-1) { // 不连通
return -1ll;
}
pos=minid;
vis[pos]=1;
used[pos][pre[pos]]=used[pre[pos]][pos]=1;
ans+=dis[pos];
for(int j=1; j<=n; ++j) {
if(vis[j]&&j!=pos) {
path[pos][j]=path[j][pos]=max(path[j][pre[pos]]*1ll,dis[pos]);
} else {
if(!vis[j]&&dis[j]>G[j][pos]) {
dis[j]=G[j][pos];
pre[j]=pos;
}
}
}
}
return ans;
}
ll SecPrim(ll prim) { // 参数是Prim算法的结果,也就是最小生成树的权值
ll ans=infll;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
if(i!=j&&!used[i][j]) {
ans=min(ans,prim-path[i][j]+G[i][j]);
}
}
}
return ans;
}
