社区讨论

萌新悬关求助,生成树+倍增LCA,但是10ptsWA

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo2fvp17
此快照首次捕获于
2023/10/23 13:10
2 年前
此快照最后确认于
2023/10/23 13:10
2 年前
查看原帖
rt,就是跑一遍最大生成树之后在LCA过程中记录最小限重,但是写挂了
CPP
#include<bits/stdc++.h>
#define inf INT_MAX
using namespace std;
struct node{int u,v,w;}e[50005];
vector<node>e2[10005];
bool vis[10005];
int n,m,q;
int fa[10005];
int f[10005][15],dep[10005],lg[10005],minw[10005][15];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool cmp(node x,node y){return x.w>y.w;}
void kruskal(int cnt=n-1){
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(!cnt)break;
		int u=find(e[i].u),v=find(e[i].v);
		if(u^v){
			fa[u]=v,--cnt;
			e2[e[i].u].push_back({e[i].u,e[i].v,e[i].w});
			e2[e[i].v].push_back({e[i].v,e[i].u,e[i].w});
		}
	}
}
void dfs(int u,int fath){
	vis[u]=1,dep[u]=dep[fath]+1,f[u][0]=fath;
	for(int i=1;i<=lg[dep[u]];i++){
		minw[u][i]=min(minw[u][i-1],minw[f[u][i-1]][i-1]);
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=0;i<e2[u].size();i++){
		if(e2[u][i].v^fath)minw[e2[u][i].v][0]=e2[u][i].w,dfs(e2[u][i].v,u);
	}
}
int lca(int x,int y,int res=inf){
	if(find(x)^find(y))return -1;
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y]){
		res=min(res,minw[x][lg[dep[x]-dep[y]]]);
		x=f[x][lg[dep[x]-dep[y]]];
	}
	if(x==y)return res;
	for(int i=lg[dep[x]];i>=0;i--){
		if(f[x][i]^f[y][i]){
			res=min(res,min(minw[x][i],minw[y][i]));
			x=f[x][i],y=f[y][i];
		}
	}
	res=min(res,min(minw[x][0],minw[y][0]));
	return res;
}
int main(){
	memset(minw,inf,sizeof minw);
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
	fa[1]=1;
	for(int i=2;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i),fa[i]=i;
	kruskal();
	for(int i=1;i<=n;i++){
		if(!vis[i])dfs(i,0);
	}
	cin>>q;
	for(int i=1,x,y;i<=q;i++){
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
}

回复

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

正在加载回复...