严格次小生成树()

[BJWC2010] 严格次小生成树

大体思路

不能算题解吧,就是简简单单记录一下,防止自己再忘了。

21 年暑假才学 LCA 时做过一下,但是一直 90。现在 22 年终于过了。

次小生成树一定只有一条边与最小生成树不同,具体证明看别的博客吧。

于是在求出最小生成树以及构成的树边之后可以枚举每条非树边,求两端点的路径上的最大值并替换,记录最值。

但是因为是严格次小,所以要路径上记录最大值和次大值,以防枚举的这条边的值和最大值一样。

算法流程:

  • 求最小生成树
  • bfs 预处理树上的信息,包括最大和次大值。
  • 枚举每条非树边,求 LCA 的过程中记录最大和次大值。
  • 记录答案

这道题注意的几个点

  • 答案的初始值要很大(我开的1e18)。
  • 要判断自环(重边看情况,Kruscal 不用判)。
  • 记录最大值和次大值的过程要注意去重,因为是严格!!!(我直接丢到一个数组里面,排序去重)。
  • LCA 不要写错了(我因为一个等号写掉调了 1h)。
  • 基记得初始化。

Code Time

#include<bits/stdc++.h>
using namespace std;
#define int long long

inline int read(){
	int sum=0,f=1;char a=getchar();
	while(a<'0' || a>'9'){if(a=='-') 	f=-1;a=getchar();}
	while(a>='0' && a<='9') 	sum=sum*10+a-'0',a=getchar();
	return sum*f;
}

const int N=1e5+5,M=6e5+5;
vector<int> ed[N],l[N];
struct node{
	int x,y,z,mrk;
}e[M];
int fa[N][30],len[N][30][2],d[N];
int n,m,mi,ans=1e18;
int f[N];
int t1,t2;

int fi(int x){
	if(f[x]==x)	return x;
	return f[x]=fi(f[x]);
}
void mer(int x,int y){f[fi(x)]=fi(y);}
bool cmp(node _,node __){return _.z<__.z;}
void get_ma(int a1,int a2,int a3,int a4){
	int a[5]={0,a1,a2,a3,a4};
	sort(a+1,a+5);int tmp=unique(a+1,a+5)-a-1;
	t1=a[tmp],t2=a[tmp-1];
}
void kru(){
	sort(e+1,e+m+1,cmp);
	int cnt=0;
	for(int i=1;i<=n;++i)	f[i]=i;
	for(int i=1;i<=m;++i){
		if(fi(e[i].x)!=fi(e[i].y)){
			++cnt;
			mer(e[i].x,e[i].y);
			mi+=e[i].z,e[i].mrk=1;
			ed[e[i].x].push_back(e[i].y);
			l[e[i].x].push_back(e[i].z);
			ed[e[i].y].push_back(e[i].x);
			l[e[i].y].push_back(e[i].z);
		}
		if(cnt==n-1)	return;
	}
}
void bfs(){
	queue<int> q;
	q.push(1);d[1]=1;
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=0;i<ed[x].size();++i){
			int y=ed[x][i];
			if(d[y])	continue;
			d[y]=d[x]+1,fa[y][0]=x,len[y][0][1]=l[x][i];
			q.push(y);
			for(int j=1;j<=20;++j)
				fa[y][j]=fa[fa[y][j-1]][j-1];
			for(int j=1;j<=20;++j){
				get_ma(len[y][j-1][1],len[y][j-1][0],len[fa[y][j-1]][j-1][1],len[fa[y][j-1]][j-1][0]);
				len[y][j][1]=t1,len[y][j][0]=t2;
			}
		}
	} 
}
void lca(int x,int y){
	t1=-1,t2=-1;
	if(d[x]<d[y])	swap(x,y);
	for(int i=20;i>=0;--i)
		if(d[fa[x][i]]>=d[y]){
			get_ma(t1,t2,len[x][i][0],len[x][i][1]);
			x=fa[x][i];
		}
	if(x==y)	return;
	for(int i=20;i>=0;--i)
		if(fa[x][i]!=fa[y][i]){
			get_ma(t1,t2,len[x][i][0],len[x][i][1]);
			get_ma(t1,t2,len[y][i][0],len[y][i][1]);
			x=fa[x][i],y=fa[y][i];
		}
	get_ma(t1,t2,len[x][0][0],len[x][0][1]);
	get_ma(t1,t2,len[y][0][0],len[y][0][1]);
}

signed main(){
	
	int x,y,z;
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		e[i].x=read(),e[i].y=read(),e[i].z=read();
		if(e[i].x==e[i].y)	--i,--m;
	}
	
	kru();bfs();
	
	for(int i=1;i<=m;++i)
		if(!e[i].mrk){
			lca(e[i].x,e[i].y);
			ans=min(ans,mi+e[i].z-t2);
			if(e[i].z!=t1)	ans=min(ans,mi+e[i].z-t1);
		}
	printf("%lld",ans);
	
	return 0;
} 
————————

[BJWC2010] 严格次小生成树

大体思路

不能算题解吧,就是简简单单记录一下,防止自己再忘了。

21 年暑假才学 LCA 时做过一下,但是一直 90。现在 22 年终于过了。

次小生成树一定只有一条边与最小生成树不同,具体证明看别的博客吧。

于是在求出最小生成树以及构成的树边之后可以枚举每条非树边,求两端点的路径上的最大值并替换,记录最值。

但是因为是严格次小,所以要路径上记录最大值和次大值,以防枚举的这条边的值和最大值一样。

算法流程:

  • 求最小生成树
  • bfs 预处理树上的信息,包括最大和次大值。
  • 枚举每条非树边,求 LCA 的过程中记录最大和次大值。
  • 记录答案

这道题注意的几个点

  • 答案的初始值要很大(我开的1e18)。
  • 要判断自环(重边看情况,Kruscal 不用判)。
  • 记录最大值和次大值的过程要注意去重,因为是严格!!!(我直接丢到一个数组里面,排序去重)。
  • LCA 不要写错了(我因为一个等号写掉调了 1h)。
  • 基记得初始化。

Code Time

#include<bits/stdc++.h>
using namespace std;
#define int long long

inline int read(){
	int sum=0,f=1;char a=getchar();
	while(a<'0' || a>'9'){if(a=='-') 	f=-1;a=getchar();}
	while(a>='0' && a<='9') 	sum=sum*10+a-'0',a=getchar();
	return sum*f;
}

const int N=1e5+5,M=6e5+5;
vector<int> ed[N],l[N];
struct node{
	int x,y,z,mrk;
}e[M];
int fa[N][30],len[N][30][2],d[N];
int n,m,mi,ans=1e18;
int f[N];
int t1,t2;

int fi(int x){
	if(f[x]==x)	return x;
	return f[x]=fi(f[x]);
}
void mer(int x,int y){f[fi(x)]=fi(y);}
bool cmp(node _,node __){return _.z<__.z;}
void get_ma(int a1,int a2,int a3,int a4){
	int a[5]={0,a1,a2,a3,a4};
	sort(a+1,a+5);int tmp=unique(a+1,a+5)-a-1;
	t1=a[tmp],t2=a[tmp-1];
}
void kru(){
	sort(e+1,e+m+1,cmp);
	int cnt=0;
	for(int i=1;i<=n;++i)	f[i]=i;
	for(int i=1;i<=m;++i){
		if(fi(e[i].x)!=fi(e[i].y)){
			++cnt;
			mer(e[i].x,e[i].y);
			mi+=e[i].z,e[i].mrk=1;
			ed[e[i].x].push_back(e[i].y);
			l[e[i].x].push_back(e[i].z);
			ed[e[i].y].push_back(e[i].x);
			l[e[i].y].push_back(e[i].z);
		}
		if(cnt==n-1)	return;
	}
}
void bfs(){
	queue<int> q;
	q.push(1);d[1]=1;
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=0;i<ed[x].size();++i){
			int y=ed[x][i];
			if(d[y])	continue;
			d[y]=d[x]+1,fa[y][0]=x,len[y][0][1]=l[x][i];
			q.push(y);
			for(int j=1;j<=20;++j)
				fa[y][j]=fa[fa[y][j-1]][j-1];
			for(int j=1;j<=20;++j){
				get_ma(len[y][j-1][1],len[y][j-1][0],len[fa[y][j-1]][j-1][1],len[fa[y][j-1]][j-1][0]);
				len[y][j][1]=t1,len[y][j][0]=t2;
			}
		}
	} 
}
void lca(int x,int y){
	t1=-1,t2=-1;
	if(d[x]<d[y])	swap(x,y);
	for(int i=20;i>=0;--i)
		if(d[fa[x][i]]>=d[y]){
			get_ma(t1,t2,len[x][i][0],len[x][i][1]);
			x=fa[x][i];
		}
	if(x==y)	return;
	for(int i=20;i>=0;--i)
		if(fa[x][i]!=fa[y][i]){
			get_ma(t1,t2,len[x][i][0],len[x][i][1]);
			get_ma(t1,t2,len[y][i][0],len[y][i][1]);
			x=fa[x][i],y=fa[y][i];
		}
	get_ma(t1,t2,len[x][0][0],len[x][0][1]);
	get_ma(t1,t2,len[y][0][0],len[y][0][1]);
}

signed main(){
	
	int x,y,z;
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		e[i].x=read(),e[i].y=read(),e[i].z=read();
		if(e[i].x==e[i].y)	--i,--m;
	}
	
	kru();bfs();
	
	for(int i=1;i<=m;++i)
		if(!e[i].mrk){
			lca(e[i].x,e[i].y);
			ans=min(ans,mi+e[i].z-t2);
			if(e[i].z!=t1)	ans=min(ans,mi+e[i].z-t1);
		}
	printf("%lld",ans);
	
	return 0;
}