求助,全红
查看原帖
求助,全红
1113701
liu_jia_lin楼主2024/11/25 19:26
#include<bits/stdc++.h>
using namespace std;
const int mxN=1e5+1;
int n,m,q,fa[mxN],dep[mxN],toFa[mxN],vis[mxN],dp[mxN][32],dpm[mxN][32];
vector<int>ve[mxN],vw[mxN],sm;
struct edge{
	int u,v,w;
}e[5*mxN];
bool cmp(edge a,edge b){
	return a.w>b.w;
}
int find_root(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find_root(fa[x]);
}
void Kruscal(){
	for(int i=1;i<=n;i++) fa[i]=i;
	stable_sort(e+1,e+1+n,cmp);
	for(int i=1;i<=m;i++){
		int ur=find_root(e[i].u),vr=find_root(e[i].v);
		if(ur!=vr){
			fa[ur]=vr;
			ve[e[i].u].push_back(e[i].v),vw[e[i].u].push_back(e[i].w);
			ve[e[i].v].push_back(e[i].u),vw[e[i].v].push_back(e[i].w);
		}
	}
}
void DFS(int r){
	vis[r]=1;
	for(int i=0;i<ve[r].size();i++){
		int j=ve[r][i],w=vw[r][i];
		if(vis[i]==0){
			dep[j]=dep[r]+1;
			fa[j]=r;
			toFa[j]=w;
		}
	}
}
void DP(){
	for(int i=1;i<=n;i++) dp[i][0]=fa[i],dpm[i][0]=toFa[i];
	int mxj=log2(n)+1;
	for(int j=1;j<=mxj;j++)
		for(int i=1;i<=n;i++){
			dp[i][j]=dp[dp[i][j-1]][j-1];
			dpm[i][j]=min(dpm[i][j-1],dpm[dp[i][j-1]][j-1]);
		}
}
int LCA(int a,int b){
	int mi=INT_MAX;
	if(dep[a]<dep[b]) swap(a,b);
	int mxj=log2(dep[a]-dep[b])+1;
	for(int j=mxj;j>=0;j--)
		if(dep[dp[a][j]]>=dep[b]){
			mi=min(mi,dpm[a][j]);
			a=dp[a][j];
		}
	if(a==b) return mi;
	mxj=log2(n)+1;
	for(int j=mxj;j>=0;j--)
		if(dp[a][j]!=dp[b][j]){
			mi=min(mi,min(dpm[a][j],dpm[b][j]));
			a=dp[a][j],b=dp[b][j];
		}
	mi=min(mi,min(dpm[a][0],dpm[b][0]));
	if(dp[a][0]==0&&dp[b][0]) return -1;
	else return mi;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	Kruscal();
	for(int i=1;i<=n;i++)
		if(fa[i]==i){
			dep[i]=1;
			fa[i]=0;
			DFS(i);
		}
	DP();
	cin>>q;
	for(int i=1;i<=q;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d/n",LCA(x,y));
	}
} 
2024/11/25 19:26
加载中...