Fork me on GitHub

浅谈次小生成树

发表于 | 分类于
字数统计: 1,332字 | 阅读时长 ≈ 7分钟

次小生成树

定义

顾名思义,在一个图$G=(V,E)$中如果存在最小生成树$T$，如果有一个生成树$T’ \not= T $且对于$\forall T_x > T’$,则称生成树$T’$为$G$的次小生成树.

算法0

枚举原来$T$中每一条边将其删去,每次求一遍MST.

复杂度:$O(n*mlog_2m)$

显然难以接受.

应该还是挺好写的(但是并不保证严格)

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

const int maxn = 3010;
struct Node{
	int u,v,c;
	bool operator < (const Node &b) const {
		return c < b.c;
	}
	bool sel;
}a[maxn];

int fa[maxn],sell[maxn],cnt = 0,n,m,ans = INT_MAX;
void Pre(void){for(int i = 1; i < maxn; i++) fa[i] = i;}

int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
inline int read(void){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){f=c=='-'?-1:1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x * f;
}
int main(int argc, char *argv[])
{
	n = read(), m = read();
	for (int i = 1; i <= m; i++)
		a[i].u = read(),a[i].v = read(),a[i].c = read(),a[i].sel = 1;
	Pre();
	sort(a+1,a+m+1);
	int ltotal = 0;
	for (int i = 1; i <= m; i++)
	{
		if (ltotal == n - 1) break;
		int fax = getf(a[i].u),fay = getf(a[i].v);
		if (fax == fay) continue;
		fa[fax] = fay;
		++ltotal;
		sell[++cnt] = i;
	}
	for (int i = 1; i <= cnt; i++)
	{
		Pre();
		int ret = 0;
		a[sell[i]].sel = 0;
		int lt = 0;
		for (int j = 1; j <= m; j++)
		{
			if (!a[j].sel) continue;
			if (lt == n - 1) break;
			int fax = getf(a[j].u),fay = getf(a[j].v);
			if (fax == fay) continue;
			fa[fax] = fay;
			++lt;
			ret += a[j].c;
		}
		if (lt == n - 1) ans = min(ans,ret);
		a[sell[i]].sel = 1;
	}
	printf("%d\n",ans);
	return 0;
}
（还能接受的）算法

倍增LCA（似乎ST表也可以） + MST

定理:如果图G的边的个数E和个点的个数N不满足关系E + 1 = N,那么存在边(u,v) 属于 T 和(x, y)不属于T满足T \ (u, v) U (x, y)是图的一颗次小生成树.

根据这个定理,记录下原最小生成树中的边,

然后枚举它的邻边并尝试添入并删去环中（如果有）最长的边,取权值的最小值即可.

置于怎么求最小生成树中$X \ to \ Y$的最短距离,可以树形dp或者LCA.

辣鸡的我（拉拉板子）写了个倍增,跑的还行吧…

LUOGU模板传送

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int SIZE = 1e5+10;
vector<int>a[SIZE];
int f[SIZE],fa[25][SIZE],dep[SIZE];
int d[2][25][SIZE],n,m,ret,ans = LLONG_MAX,mx;
bool used[SIZE << 2],vis[SIZE];
struct Edge{
    int from,to,val;
    bool operator < (const Edge y){
        return val < y.val;
    }
}e[SIZE<<2];
inline int read(void) {
	int x = 0,f = 1;
	char c = getchar();
	while(!isdigit(c)) {
		f = c == '-' ? -1 : 1;
		c = getchar();
	}
	while(isdigit(c)) {
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * f;
}
int F(int x){return x==f[x]?x:f[x]=F(f[x]);} 
void kruskal() 
{
	sort(e,e+m);
	int Lfs=n-1;
	for(int i=1; i<=n; ++i) f[i]=i;
	for(int i=0; i<m && Lfs; ++i) {
		int x=F(e[i].from),y=F(e[i].to);
		if(x!=y) {
			f[x]=y;ret+=e[i].val;used[i]=1;
			--Lfs;mx=max(mx,e[i].val);  
		}
	}
}
void dfs(int x) {
	vis[x]=true;
	for(int i=1; i<=23; ++i) {
		fa[i][x]=fa[i-1][fa[i-1][x]];
		int t1=d[0][i-1][x], t2=d[0][i-1][fa[i-1][x]];
		d[0][i][x]=max(t1 ,t2);
		d[1][i][x]=max(d[1][i-1][x] , d[1][i-1][fa[i-1][x]]);
		if(t1!=t2) d[1][i][x]=max(d[1][i][x] , min(t1 , t2));
	}
	for(int i=0; i<a[x].size(); ++i) {
		int t=e[a[x][i]].to+e[a[x][i]].from-x;
		if(vis[t]) continue;   
		dep[t]=dep[x]+1;
		fa[0][t]=x;
		d[0][0][t]=e[a[x][i]].val;
		dfs(t);
	}
}
int lca(int u,int v) {
	if(dep[u]<dep[v])
		swap(u,v);
	if(dep[u]!=dep[v]) {
		for(int i=23,h=dep[u]-dep[v]; i>=0; --i)
			if(h&(1<<i)) u=fa[i][u];
	}
	if(u == v) return u;
	for(int i=23; i>=0; --i) if(fa[i][u]!=fa[i][v])
			u=fa[i][u] , v=fa[i][v];
	return fa[0][u];
}
int get(int u,int v,int c) {
	int fht=lca(u,v);
	int m1=-1,m2=-1;
	for(int i=23,h1=dep[u]-dep[fht],h2=dep[v]-dep[fht]; i>=0; --i) {
		if(h1&(1<<i)) {
			if(d[0][i][u]>m1) m2=m1,m1=d[0][i][u];
			m2=max(m2 , d[1][i][u]);
		}
		if(h2&(1<<i)) {
			if(d[0][i][v]>m1) m2=m1,m1=d[0][i][v];
			m2=max(m2 , d[1][i][v]);
		}
	}
	//严格大于的关键,这里若是return没有处理好极其容易被Hack 
	if(m1!=c) return c-m1;
	if(m2!=-1) return c-m2;
	return 0; 
}
signed main(signed argc, char *argv[]) 
{
	n = read(), m = read();
	for(int i=0; i<m; ++i) { 
		int u,v,w;
		u = read(),v = read(),w = read();
			e[i]=(Edge){u,v,w};
	}
	kruskal();  
	for(int i=0; i<m; ++i) if(used[i]) { 
			a[e[i].from].push_back(i);
			a[e[i].to].push_back(i);
		}
	dep[1]=1;dfs(1); 
	for(int i=0; i<m; ++i) if(!used[i]) { 
			if(e[i].val-mx>ans) break; int t=get(e[i].from,e[i].to,e[i].val); if(t) ans=min(ans,t); 
		}
	printf("%lld\n",ret+ans);
	return 0;
}

听说好像有大爷还用LCT来维护这个X到Y的最大值,给跪了啊