subtask1一个点wa了,求助
查看原帖
subtask1一个点wa了,求助
752094
MornHus楼主2023/2/2 12:44

只有一个点wa了,不知道为啥

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x;
}
struct line{
	int to,val;
};
struct lines{
	int u,v,w;
}l[50001];
int n,m,q;
int f[10001];


int dep[10001];
int fa[10001][15];
int w[10001][15];
vector<line>tree[10001];
bool cmp(lines a,lines b){
	return a.w>b.w;
}
int find(int x){   
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void unity(int x,int y){
	x=find(x);
	y=find(y);
	if(x!=y)f[x]=y;
}
void dfs(int now,int father,int we){
	dep[now]=dep[father]+1;
	w[now][0]=we;
	fa[now][0]=father;
	for(int i=1;i<=14;i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];
		w[now][i]=min(w[now][i-1],w[fa[now][i-1]][i-1]);
	}
	for(int i=0;i<tree[now].size();i++){
		if(tree[now][i].to==father)continue;
		dfs(tree[now][i].to,now,tree[now][i].val);
	}
}
int lca(int u,int v){
	int ans=inf;
	if(find(u)!=find(v))return -1;
	if(dep[u]<dep[v])swap(u,v);
	for(int i=14;i>=0;i--){
		if(fa[u][i]&&dep[fa[u][i]]>=dep[v]){
			ans=min(ans,w[u][i]);
			u=fa[u][i];
		}
	}
	if(u==v){
		return ans;
	}
	for(int i=14;i>=0;i--){
		if(fa[u][i]&&fa[v][i]&&fa[u][i]!=fa[v][i]){
			ans=min(min(w[u][i],w[v][i]),ans);
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return min(min(w[u][0],w[v][0]),ans);
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=m;i++){
		l[i].u=read();
		l[i].v=read();
		l[i].w=read();
	}
	sort(l+1,l+m+1,cmp);
	int t=0;
	for(int i=1;i<=m;i++){
		if(find(l[i].u)!=find(l[i].v)){
			unity(l[i].u,l[i].v);
			tree[l[i].u].push_back({l[i].v,l[i].w});
			tree[l[i].v].push_back({l[i].u,l[i].w});
			t++;
			if(t==n-1)break;
		}
	}
	dfs(1,0,0);
	q=read();
	for(int i=1;i<=q;i++){
		int a, b;
		a=read();
		b=read();
		
		printf("%d\n",lca(a,b));
	}
	return 0;
}
2023/2/2 12:44
加载中...