社区讨论

只有输出-1时对,求助qwq

P1967[NOIP 2013 提高组] 货车运输参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo8ay816
此快照首次捕获于
2023/10/27 15:39
2 年前
此快照最后确认于
2023/10/27 15:39
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define N 100086
using namespace std;
int n,m,q,cnt;
int fa[N],head[N],f[N][32],w[N][32],death[N];
bool vis[N];
struct sb {
	int x,y,num;
} a[N];
bool cmp(sb a,sb b) {
	return a.num>b.num;
}
struct sd {
	int next,to,w;
} edge[N];
void add(int from,int to,int w) {
	edge[++cnt].next=head[from];
	edge[cnt].to=to,edge[cnt].w=w;
	head[from]=cnt;
}
int find(int x) {
	if(fa[x]==x)return x;
	else return fa[x]=find(fa[x]);
}
void ssb() {
	sort(a+1,a+m+1,cmp);
	for(int i=1; i<=n; i++)fa[i]=i;
	for(int i=1; i<=m; i++) {
		if(find(a[i].x)!=find(a[i].y)) {
			fa[find(a[i].x)]=find(a[i].y);
			add(a[i].x,a[i].y,a[i].num);
			add(a[i].y,a[i].x,a[i].num);
		}
	}
}
void dfs(int x) {
	vis[x]=1;
	for(int i=head[x]; i; i=edge[i].next) {
		if(vis[edge[i].to])continue;
		death[edge[i].to]=death[x]+1;
		f[edge[i].to][0]=x;
		w[edge[i].to][0]=edge[i].w;
		dfs(edge[i].to);
	}
}
int lca(int x,int y) {
	if(find(x)!=find(y))return -1;
	int ans=2147483647;
	if(death[x]>death[y])swap(x,y);
	for(int i=20; i>=0; i--)
		if(death[f[y][i]]>=death[x]) ans=min(ans,w[y][i]),y=f[y][i];
	if(x==y) return ans;
	for(int i=20; i>=0; i--)
		if(f[x][i]!=f[y][i]) ans=min(w[x][i],w[y][i]),x=f[x][i],y=f[y][i];
	ans=min(ans,min(w[x][0],w[y][0]));
	return ans;
}
int main() {
	cin>>n>>m;
	int x,y,z;
	for(int i=1; i<=m; i++)
		cin>>a[i].x>>a[i].y>>a[i].num;
	ssb();
	for(int i=1; i<=n; i++) {
		if(!vis) {
			death[i]=1;
			dfs(i);
			f[i][0]=i;
			w[i][0]=2147483647;
		}
	}
	for(int i=1; i<=20; i++)
		for(int j=1; j<=n; j++) {
			f[j][i]=f[f[j][i-1]][i-1];
			w[j][i]=min(w[j][i-1],w[f[j][i-1]][i-1]);
		}
	cin>>q;
	for(int i=1; i<=q; i++) {
		cin>>x>>y;
		cout<<lca(x,y)<<'\n';
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...