Abensyl's Blog

精于心，简于言，勤于思，善于行

次小生成树

发布于 2023-10-28 | 标签: 图论 | 15分钟 | 2695字数

前置知识

回顾求解最小生成树的算法，有两种：kruskal 和 prim。

Kruskal 最小生成树。
Prim 最小生成树。

非严格最小生成树

求次小生成树的第一步就是先求解最小生成树，那么在生成最小生成树后，很容易想到如下操作：

说明：以下的描述中均是 nn 点 mm 边无向图，nn 就表示点数，mm 表示图的总边数，树边表示原最小生成树上的边，非树边即不是原最小生成树上的边。

进行替换，对于替换操作，实际上就是对于生成树，找到一个非树边（不在原最小生成树中的边），把它与最小生成树中的边进行替换，那么，我们把非树边加入原最小生成树中，很明显，原本的最小生成树会变成一个 nn 点 nn 边的基环树，对于这棵基环树，若要求次小生成树，应找到形成的环中除了加入边之外的最长边，将其删除，这样就可以将基环树破为树了，只需要枚举每一条非树边，然后对于形成的环进行枚举，即可得到答案。

correctness

  1. 至少有一条边在次小生成树中而不在最小生成树中。

证明：显然。

  1. 证明次小生成树一定包含 n−2n-2 条最小生成树边和仅一条非树边组成的，而不是大于一条非树边：

由结论 11 我们可以得到某条在次小生成树而不在最小生成树上的边，我们称它为 ee。
显然 ee 是条无用边，因为它不在 MST 上。
对于最小生成树，我们添加一个非树边，这个非树边会和原生成树形成一个环，很显然，加入的这条非树边 ee 肯定是整个环中边权最大的边，也就是说，对于每一个原图中的环，最小生成树破环的方式都一定是最优的，那么，也就是说，我们往环中加边只会让答案更劣，所以就需要加的边尽可能的少，又因为结论 11，至少有一条变为非树边，所以由此可知，有且仅有一条非树边在次小生成树中。

  1. 任意无用边的对应最小生成树肯定不是一开始求的 MST。

证明：显然。

efficiency

对于 MST 的求解，可以用 kruskal 或 prim 通过 O(mlog⁡n)O(m\log n) 或 O(mlog⁡m)O(m\log m) 的时间复杂度解决，用哪种取决于图的稠密程度。

对于非树边，进行枚举，然后进行求环。

以下代码采用 kruskal，时间复杂度为 O(mlog⁡m+nm)O(m\log m+nm)：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct edge {
	int to,nx,wt;
} eg[N<<1];
int hd[N],tot=0;
void adeg(int u,int v,int w) {
	eg[++tot]={v,hd[u],w};
	hd[u]=tot;
}
struct dsu {
	int fa[N];
	void init(int n) {
		for(int i=1;i<=n;++i)
			fa[i]=i;
	}
	int find(int u) {
		if(fa[u]==u) return u;
		return fa[u]=find(fa[u]);
	}
	void merge(int u,int v) {
		u=find(u),v=find(v);
		if(u==v) return;
		fa[u]=v;
	}
} d;
struct node {
	int u,v,w;
	bool operator < (const node a) const {
		return w<a.w;
	}
} ed[N<<1];
bitset<N<<1> in;
int kruskal(int n,int m) {
	d.init(n);
	sort(ed+1,ed+m+1);
	int tot=0,sum=0;
	for(int i=1;i<=m;++i) {
		int u=ed[i].u,v=ed[i].v,w=ed[i].w;
		if(d.find(u)==d.find(v)) continue;
		d.merge(u,v);
		in[i]=true;
		adeg(u,v,w);
		adeg(v,u,w);
		sum+=w;
		tot++;
	}
	if(tot!=n-1) return -1;
	return sum;
}
int dep[N];
int f[N][18];
void dfs(int u,int fa) {
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<18;++i)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=hd[u];i;i=eg[i].nx) {
		int to=eg[i].to;
		if(to==fa) continue;
		dfs(to,u);
	}
}
int lca(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=17;i>=0;--i)
		if(dep[f[u][i]]>=dep[v])
			u=f[u][i];
	for(int i=17;i>=0;--i)
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	if(u==v) return u;
	return f[u][0];
}
vector<int> stk;
void findpath(int u,int d) {
	if(u==d)
		return;
	for(int i=hd[u];i;i=eg[i].nx) {
		int to=eg[i].to;
		if(dep[to]>dep[u]) continue;
		stk.push_back(eg[i].wt);
		findpath(to,d);
	}
}
int replace(int u,int v) {
	int lc=lca(u,v);
	int mx=-1e18;
	stk.clear();
	findpath(u,lc);
	for(auto c:stk) mx=max(mx,c);
	stk.clear();
	findpath(v,lc);
	for(auto c:stk) mx=max(mx,c);
	return mx;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),
	cout.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i) {
		int u,v,w;
		cin>>u>>v>>w;
		ed[i]={u,v,w};
	}
	int val=kruskal(n,m);
	if(val==-1) {
		cout<<"-1\n";
		return 0;
	}
	int res=1e18;
	dfs(1,0);
	for(int i=1;i<=m;++i) {
		if(in[i]) continue;
		int u=ed[i].u,v=ed[i].v,w=ed[i].w;
		int c=replace(u,v);
		res=min(res,val+w-c);
	}
	cout<<res<<'\n';
	return 0;
}

可以利用倍增或树链剖分进一步优化时间复杂度，将时间复杂度优化为 O(mlog⁡n+mlog⁡n)O(m\log n+m\log n)，即在每条重链上记录最大值或者在倍增数组中建立 st 表记录，代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct edge {
	int to,nx,wt;
} eg[N<<1];
int hd[N],tot=0;
void adeg(int u,int v,int w) {
	eg[++tot]={v,hd[u],w};
	hd[u]=tot;
}
struct dsu {
	int fa[N];
	void init(int n) {
		for(int i=1;i<=n;++i)
			fa[i]=i;
	}
	int find(int u) {
		if(fa[u]==u) return u;
		return fa[u]=find(fa[u]);
	}
	void merge(int u,int v) {
		u=find(u),v=find(v);
		if(u==v) return;
		fa[u]=v;
	}
} d;
struct node {
	int u,v,w;
	bool operator < (const node a) const {
		return w<a.w;
	}
} ed[N<<1];
bitset<N<<1> in;
int kruskal(int n,int m) {
	d.init(n);
	sort(ed+1,ed+m+1);
	int tot=0,sum=0;
	for(int i=1;i<=m;++i) {
		int u=ed[i].u,v=ed[i].v,w=ed[i].w;
		if(d.find(u)==d.find(v)) continue;
		d.merge(u,v);
		in[i]=true;
		adeg(u,v,w);
		adeg(v,u,w);
		sum+=w;
		tot++;
	}
	if(tot!=n-1) return -1;
	return sum;
}
int dep[N];
int f[N][18],st[N][18];
void dfs(int u,int fa) {
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<18;++i)
		f[u][i]=f[f[u][i-1]][i-1],
		st[u][i]=max(st[u][i-1],st[f[u][i-1]][i-1]);
	for(int i=hd[u];i;i=eg[i].nx) {
		int to=eg[i].to;
		if(to==fa) continue;
		st[to][0]=eg[i].wt;
		dfs(to,u);
	}
}
int lca(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=17;i>=0;--i)
		if(dep[f[u][i]]>=dep[v])
			u=f[u][i];
	for(int i=17;i>=0;--i)
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	if(u==v) return u;
	return f[u][0];
}
int findpath(int u,int d) {
	int mx=-1e18;
	for(int i=17;i>=0;--i)
		if(dep[f[u][i]]>=dep[d])
			mx=max(st[u][i],mx),
			u=f[u][i];
	return mx;
}
int replace(int u,int v) {
	int lc=lca(u,v);
	int mx=max(findpath(u,lc),findpath(v,lc));
	return mx;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),
	cout.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i) {
		int u,v,w;
		cin>>u>>v>>w;
		ed[i]={u,v,w};
	}
	int val=kruskal(n,m);
	if(val==-1) {
		cout<<"-1\n";
		return 0;
	}
	int res=1e18;
	dfs(1,0);
	for(int i=1;i<=m;++i) {
		if(in[i]) continue;
		int u=ed[i].u,v=ed[i].v,w=ed[i].w;
		int c=replace(u,v);
		res=min(res,val+w-c);
	}
	cout<<res<<'\n';
	return 0;
}

练习题

Timus1416. Confidential

严格次小生成树

刚才在非严格次小生成树中，我们的删边做法是：找到形成的环中除了加入边之外的最长边，将其删除。

那么，如果我们删去的这条边与加入的那条边权值相同，那么实际上就等于改变了树的构造，但实际上还是最小生成树，所以不严格。

如要求解严格次小生成树，那么必须保证替换的边与删除的边权值不同，所以，如果最大值与替换边的权值相同，那么我们就需要用严格次大指来替换，只要改变一下刚才 st 表的构造，同时记录最大值和严格次大值即可，代码如下：

#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5;
struct edge {
	int to,nx,wt;
} eg[N<<1];
int hd[N],tot=0;
void adeg(int u,int v,int w) {
	eg[++tot]={v,hd[u],w};
	hd[u]=tot;
}
struct dsu {
	int fa[N];
	void init(int n) {
		for(int i=1;i<=n;++i)
			fa[i]=i;
	}
	int find(int u) {
		if(fa[u]==u) return u;
		return fa[u]=find(fa[u]);
	}
	void merge(int u,int v) {
		u=find(u),v=find(v);
		if(u==v) return;
		fa[u]=v;
	}
} d;
struct node {
	int u,v,w;
	bool operator < (const node a) const {
		return w<a.w;
	}
} ed[M];
bitset<M> in;
int kruskal(int n,int m) {
	d.init(n);
	sort(ed+1,ed+m+1);
	int tot=0,sum=0;
	for(int i=1;i<=m;++i) {
		int u=ed[i].u,v=ed[i].v,w=ed[i].w;
		if(u==v) continue;
		if(d.find(u)==d.find(v)) continue;
		d.merge(u,v);
		in[i]=true;
		adeg(u,v,w);
		adeg(v,u,w);
		sum+=w;
		tot++;
	}
	if(tot!=n-1) return -1;
	return sum;
}
pii merge(pii x,pii y) {
	int a[4]={-x.first,-x.second,-y.first,-y.second};
	sort(a,a+4);
	unique(a,a+4);
	return make_pair(-a[0],-a[1]);
}
int dep[N];
int f[N][18];
pii st[N][18];
void dfs(int u,int fa) {
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<18;++i) {
		f[u][i]=f[f[u][i-1]][i-1],
		st[u][i]=merge(st[u][i-1],st[f[u][i-1]][i-1]);
	}
	for(int i=hd[u];i;i=eg[i].nx) {
		int to=eg[i].to;
		if(to==fa) continue;
		st[to][0].first=eg[i].wt;
		st[to][0].second=0;
		dfs(to,u);
	}
}
int lca(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=17;i>=0;--i)
		if(dep[f[u][i]]>=dep[v])
			u=f[u][i];
	for(int i=17;i>=0;--i)
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	if(u==v) return u;
	return f[u][0];
}
pii findpath(int u,int d) {
	pii mx={0,0};
	for(int i=17;i>=0;--i)
		if(dep[f[u][i]]>=dep[d])
			mx=merge(st[u][i],mx),
			u=f[u][i];
	return mx;
}
pii replace(int u,int v) {
	int lc=lca(u,v);
	pii mx=merge(findpath(u,lc),findpath(v,lc));
	return mx;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),
	cout.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i) {
		int u,v,w;
		cin>>u>>v>>w;
		ed[i]={u,v,w};
	}
	int val=kruskal(n,m);
	if(val==-1) {
		cout<<"-1\n";
		return 0;
	}
	int res=1e18;
	dfs(1,0);
	for(int i=1;i<=m;++i) {
		if(in[i]) continue;
		int u=ed[i].u,v=ed[i].v,w=ed[i].w,c;
		if(u==v) continue;
		pii p=replace(u,v);
		if(p.first==w) c=p.second;
		else c=p.first;
		res=min(res,val+w-c);
	}
	cout<<res<<'\n';
	return 0;
}

板子题：【洛谷 P4180】[BJWC2010] 严格次小生成树

赞赏
# 图论
最近公共祖先（LCA） 上一篇
csp 2023 游记 下一篇
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea, further developed by Abensyl, All rights reserved.
0%