洛谷 P4180 [BJWC2010]严格次小生成树

题目描述
小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:如果最小生成树选择的边集是EM,严格次小生成树选择的边集是ES,那么需要满足:和严格小于
这下小 C 蒙了,他找到了你,希望你帮他解决这个问题。

输入格式
第一行包含两个整数N 和M,表示无向图的点数与边数。 接下来 M行,每行 3个数x y z 表示,点 x 和点y之间有一条边,边的权值为z。

输出格式
包含一行,仅一个数,表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

题解:由kruskal算法,我们不难想到,在剩下没有选择的边中,我们选一条把它和在树中的图换一下,然后判断这棵新树的大小,还要存一下次小边,因为如果当前加入的边的权值与最大值相等,就不满足严格次小,所以再搞一下次小边,就阔以了
(说是好说,写可挺麻烦,我调了一上午,最后还是吸氧水过去的嘤嘤嘤

上代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 2147483647000000
#define int long long 
using namespace std;
const int M=600004;
const int N=200002;
int n,m,tot,head[M],nex[M],to[M],v[M];
int dep[N];
int w[N][31],f[N][31],minn[N][31];
bool vis[M];
int ans,cnt;
struct NODE{
   
	int x,y,z;
	bool operator < (const NODE &a){
   
		return this->z <a.z; 
	} 
}bian[M];
int fa[N];
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int find(int x) {
   //并查集找父亲 
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
inline void add2(int x,int y,int z){
   
	++tot;
	nex[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	v[tot]=z;
}
inline void kruskal(){
   
    ans=0,cnt=0;
	for(int i=1;i<=m;i++){
   
		if(fa[find(bian[i].x)]!=fa[find(bian[i].y)]){
   
		   fa[find(bian[i].x)]=fa[find(bian[i].y)];
		   cnt++;
		   vis[i]=1;
		   ans+=bian[i].z; 
		   add2(bian[i].x,bian[i].y,bian[i].z);
		   add2(bian[i].y,bian[i].x,bian[i].z);
		} 
		if(cnt==n-1) break;
	}
	return ;
}
void dfs(int x,int fath){
   
	for(int i=head[x];i;i=nex[i]){
   
		if(to[i]!=fath){
   
			dep[to[i]]=dep[x]+1;
			w[to[i]][0]=v[i];
			f[to[i]][0]=x;
			minn[to[i]][0]=-INF;
			dfs(to[i],x);
		}
	}
}
inline int lca(int x,int y){
   
	if(dep[x]>dep[y]) swap(x,y);
	for(int i=30;i>=0;i--) if(dep[x]<=dep[y]-(1<<i)) y=f[y][i];
	if(x==y) return x;
	for(int i=30;i>=0;i--) {
   
		if(f[x][i]!=f[y][i]){
   
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int qsum(int x,int y,int maxx){
   
	int maxxx=-INF;
	for(int i=30;i>=0;i--){
   
		if(dep[f[x][i]]>=dep[y]){
   
			if(maxx!=w[x][i]) maxxx=max(maxxx,w[x][i]);
			else maxxx=max(maxxx,minn[x][i]);
		}
	}
	return maxxx;
}
main(){
   
	n=read();m=read();
	for(int i=1;i<=m;i++){
   
		bian[i].x=read();bian[i].y=read();bian[i].z=read();
	}
	sort(bian+1,bian+m+1);
	for(int i=1;i<=n;i++) fa[i]=i;
	kruskal();
	dep[1]=1;
	f[1][0]=0;
	minn[1][0]=-INF;
	memset(w,0,sizeof(w));
	dfs(1,1); 
	for(int i=1;i<=30;i++){
   
		for(int j=1;j<=n;j++){
   
			f[j][i]=f[f[j][i-1]][i-1];
			w[j][i]=max(w[j][i-1],w[f[j][i-1]][i-1]);
			minn[j][i]=max(minn[j][i-1],minn[f[j][i-1]][i-1]);
			if(w[j][i-1]>w[f[j][i-1]][i-1]) minn[j][i]=max(minn[j][i],w[f[j][i-1]][i-1]);
			else if(w[j][i-1]<w[f[j][i-1]][i-1]) minn[j][i]=max(minn[j][i],w[j][i-1]);
		}
	}
	int Ans=INF;
	for(int i=1;i<=m;i++){
   
		if(!vis[i]){
   
			int x=bian[i].x;
			int y=bian[i].y;
			int k=lca(x,y); 
			int x1=qsum(x,k,bian[i].z);
			int x2=qsum(y,k,bian[i].z);
			Ans=min(Ans,ans-max(x1,x2)+bian[i].z);
		}
	}
	printf("%lld",Ans);
	return 0;
} 

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-22 16:38
江苏大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 00:27
中南大学_2023
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议