社区讨论
萌新悬关求助,生成树+倍增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 条回复,欢迎继续交流。
正在加载回复...