70分求助
查看原帖
70分求助
178994
ItzPigeon楼主2020/8/11 16:10

70分,wa了10,12,14,16,19,20,请问哪里出错了

#include<bits/stdc++.h>
#define N 10001
using namespace std;
struct node{
	int x,y,lim;
}ed[N*5];
struct node2{
	int x,lim;
};
vector<node2> to[N];
int fa[N][21],ju[N][21],f[N],dept[N];
int n,m,q,x2,y2;
bool mig[N];
bool cmp(node x,node y){
	return x.lim>y.lim;
}
int find(int t){
	if(f[t]==t) return t;
	return f[t]=find(f[t]);
}
void kruscal(){
	for(int i=1;i<=m;i++){
		if(find(ed[i].x)!=find(ed[i].y)){
			f[find(ed[i].x)]=find(ed[i].y);
			node2 tmp; tmp.x=ed[i].y; tmp.lim=ed[i].lim;
			to[ed[i].x].push_back(tmp);
			tmp.x=ed[i].x;
			to[ed[i].y].push_back(tmp);
		}
	}
}
void dfs(int t,int dep){
	dept[t]=dep;
	for(int i=0;i<to[t].size();i++)
		if(!mig[to[t][i].x]){
			mig[to[t][i].x]=true;
			fa[to[t][i].x][0]=t;
			ju[to[t][i].x][0]=to[t][i].lim;
			dfs(to[t][i].x,dep+1);
		}
}
int LCA(int x,int y){
	if(find(x)!=find(y)) return -1;
	if(dept[x]<dept[y]) swap(x,y);
	int ret=INT_MAX;
	for(int i=20;i>=0;i--){
		if(dept[fa[x][i]]>=dept[y]){
			ret=min(ret,ju[x][i]);
			x=fa[x][i];
		}
	}
	if(x==y) return ret;
	for(int i=20;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			ret=min(ret,min(ju[x][i],ju[y][i]));
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	ret=min(ret,min(ju[x][0],ju[y][0]));
	return ret;
}
int main(){
	int x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		f[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		ed[i].x=x; ed[i].y=y; ed[i].lim=z;
	}
	sort(ed+1,ed+m+1,cmp);
	kruscal();
	dfs(1,1);
	for(int i=2;i<=n;i++)
		if(dept[i]==0) dfs(i,1);
	for(int i=1;i<=20;i++)
		for(int j=1;j<=n;j++){
			fa[j][i]=fa[fa[j][i-1]][i-1];
			ju[j][i]=min(ju[j][i-1],ju[fa[j][i-1]][i-1]);
		}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}
2020/8/11 16:10
加载中...