克鲁斯卡尔重构树(Network)

2021年9月12日 15点热度 0条评论 来源: 木落淮南,雨晴雲夢

Network

要求的是, x x x y y y路径中边权某一路径的最大边权的最小值

利用克鲁斯卡尔建树,发现某两点未连,就在这两个点之间则插入一个新节点(作为这两个节点的父节点),新节点的边权,在建树完成后会形成一个新的树,其 x x x y y y路径中边权某一路径的最大边权的最小值就是其 L C A LCA LCA的权值。

另外要从新的根节点开始 d f s dfs dfs

可以参考这篇博客:

传送门

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
#define int long long
//#define double long double
#define re register int
#define void inline void
#define eps 1e-8
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
using namespace std;
const int mod=998244353;
const int M=1e9;
const int N=2e5+5;//?????????? 4e8
struct node
{ 
	int ver,next;
}e[N];
int tot,head[N];
struct tree
{ 
	int x,y,z;
}a[N];
int cnt,val[N],d[N];
int n,m,q;
int f[N][30],fa[N];
void add(int x,int y)
{ 
	e[++tot].ver=y;
	e[tot].next=head[x];
	head[x]=tot;
}
void addedge(int x,int y)
{ 
	add(x,y);add(y,x);
}
bool cmp(tree i,tree j)
{ 
	return i.z<j.z;
}
int get(int x)
{ 
	if(fa[x]==x)  return x;
	return fa[x]=get(fa[x]);
}
void dfs(int x,int pre)
{ 
	d[x]=d[pre]+1;
	for(re i=1;i<=25;i++)  f[x][i]=f[f[x][i-1]][i-1];
	for(re i=head[x];i;i=e[i].next)
	{ 
		int y=e[i].ver;
		if(y==pre)  continue;
		f[y][0]=x;
		dfs(y,x);
	}
}
int lca(int x,int y)
{ 
	if(d[x]<d[y])  swap(x,y);
	for(re i=25;i>=0;i--)  if(d[f[x][i]]>=d[y])  x=f[x][i];
	if(x==y)  return x;
	for(re i=25;i>=0;i--)  if(f[x][i]!=f[y][i])  x=f[x][i],y=f[y][i];
	return f[x][0];
}
void bulid()
{ 
	cnt=n;
	sort(a+1,a+m+1,cmp);
	for(re i=1;i<=n;i++)  fa[i]=i;
	for(re i=1;i<=m;i++)
	{ 
		int x=get(a[i].x);
		int y=get(a[i].y);
		int z=a[i].z;
		if(x==y)  continue;
		++cnt;
// x=a[i].x,y=a[i].y;
		fa[x]=fa[y]=fa[cnt]=cnt;
		addedge(x,cnt);addedge(cnt,y);
		val[cnt]=z;
	}
}
void solve()
{ 
	cin>>n>>m>>q;
	for(re i=1;i<=m;i++)  scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
	bulid();
	dfs(cnt,cnt);
	while(q--)
	{ 
		int x,y;
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",val[lca(x,y)]);
	}
}
signed main()
{ 
    int T=1;
// cin>>T;
    for(int index=1;index<=T;index++)
    { 
// printf("Case #%lld: ",index);
        solve();
// puts("");
    }
    return 0;
}
/* 2 5 1 2 3 4 5 1 2 2 3 3 4 4 5 1 1 5 1 5 1 2 3 4 5 1 2 1 3 2 4 2 5 2 4 5 2 3 4 1 */
    原文作者:木落淮南,雨晴雲夢
    原文地址: https://blog.csdn.net/lcl1234567890lcl/article/details/120252825
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。