次小生成树问题

次小生成树是这样的一个问题:给定一个图,求它生成树中第二小的。

其中生成树的大小为生成树中边权之和。

这个问题有非严格次小和严格次小两种。

算法1

暴力枚举生成树然后排序取第二小。

算法2

可以证明,一定可以在最小生成树中仅替换一条边得到次小生成树。

构造最小生成树,枚举其中每条边,删掉这条边,再在其它边中选最小的可以加进来的一条加进来。

得到的新生成树中取最小值。

那么用kruscal特别方便。

时间复杂度O(nm)O(nm)

当然对于严格次小,选的边一定要比这条边大。

算法3

kruscal构造最小生成树。

枚举每条不在生成树上的边<u,v><u,v>,把它加上去后就会出现一个环。

那么在原树上找到<u,v><u,v>之间的路径,删掉最大边,然后加上这条边即可得到新的生成树。

这些里面取最小值即可。

最大边可以通过倍增找lca计算出来。

时间复杂度O(mlogn)O(m\log n)

对于严格次小生成树,如果最大边和这条边边权一样,就要取严格次大值。

严格次大值也可以倍增计算。

这是洛谷4180 【模板】严格次小生成树 的代码。

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
Author: CNYALI_LK
LANG: C++
PROG: 4180.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
struct edge{
ll u,v,w;
};
edge e[333333];
ll fa[102424],use[333333];
ll beg[102424],to[204848],lst[204848],w[204848],dis[102424],en;
ll f[102424][20],mx1[102424][20],mx2[102424][20];
ll e_cmp(edge a,edge b){
return a.w<b.w;
}

ll find(ll x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void add(ll u,ll v,ll wa){
to[++en]=v;
lst[en]=beg[u];
beg[u]=en;
w[en]=wa;
}
void dfs(ll x,ll fa){
f[x][0]=fa;
dis[x]=dis[fa]+1;
for(ll i=beg[x];i;i=lst[i])if(to[i]!=fa){
dfs(to[i],x);
}
else mx1[x][0]=w[i];
}

void upd(ll &mx1,ll &mx2,ll mxx1,ll mxx2){
ll nm=max(mx1,mxx1),inm=0;
if(mx1==nm)chkmax(inm,mx2);
else chkmax(inm,mx1);

if(mxx1==nm)chkmax(inm,mxx2);
else chkmax(inm,mxx1);
mx1=nm;
mx2=inm;
}
void build(ll n,ll t){
for(ll j=1;j<=t;++j)for(ll i=1;i<=n;++i){
f[i][j]=f[f[i][j-1]][j-1];
mx1[i][j]=mx1[i][j-1];
mx2[i][j]=mx2[i][j-1];
upd(mx1[i][j],mx2[i][j],mx1[f[i][j-1]][j-1],mx2[f[i][j-1]][j-1]);
}
}
ll _lca(edge e){
ll u=e.u,v=e.v,w=e.w,max1=0,max2=0;
if(dis[u]<dis[v])swap(u,v);
for(ll i=18;~i;--i){
if(dis[u]-(1<<i)>=dis[v]){
upd(max1,max2,mx1[u][i],mx2[u][i]);
u=f[u][i];
}
}
for(ll i=18;~i;--i){
if(f[u][i]!=f[v][i]){
upd(max1,max2,mx1[u][i],mx2[u][i]);
upd(max1,max2,mx1[v][i],mx2[v][i]);
u=f[u][i];
v=f[v][i];
}
}
if(u!=v){
ll i=0;
upd(max1,max2,mx1[u][i],mx2[u][i]);
upd(max1,max2,mx1[v][i],mx2[v][i]);
u=f[u][i];
v=f[v][i];
}
if(max1==w)if(max2)return w-max2;else return 0x3f3f3f3f3f3f3f3f;
else return w-max1;
}

int main(){
#ifdef cnyali_lk
freopen("4180.in","r",stdin);
freopen("4180.out","w",stdout);
#endif
ll n,m;
n=read();m=read();
for(ll i=1;i<=m;++i){
e[i].u=read();
e[i].v=read();
e[i].w=read();

}
sort(e+1,e+m+1,e_cmp);
for(ll i=1;i<=n;++i)fa[i]=i;
ll q=n;
ll sum=0,ans=0x3f3f3f3f3f3f3f3f;
for(ll i=1;q>1;++i)if(find(e[i].u)!=find(e[i].v)){
add(e[i].v,e[i].u,e[i].w);
add(e[i].u,e[i].v,e[i].w);
sum+=e[i].w;
fa[find(e[i].u)]=find(e[i].v);
use[i]=1;
--q;
}
dfs(1,0);
build(n,18);
for(ll i=1;i<=m;++i)if(!use[i]){
chkmin(ans,sum+_lca(e[i]));
}
printf("%lld\n",ans);
return 0;

}

文章目录
  1. 1. 算法1
  2. 2. 算法2
  3. 3. 算法3
|