怎么调都不对,求大佬帮看以下,感觉自己写的还是很清晰的(哭)
#include<bits/stdc++.h>
using namespace std;
//定义变量
int n,m,q;
int dep[10050],lg[10050];
int f[10050][22];
int fa[10050][22];
//原图边及比较函数,并查集
struct pedge
{
int u,v,w;
}pe[50050];
bool cmp(pedge x,pedge y)
{
return x.w>y.w;
}
int pfa[10050];
int find(int x)
{
return pfa[x]==x?x:pfa[x]==x;
}
//建树后的边,链式前向星存图
struct edge
{
int nxt,w,to;
}e[50050*2];
int head[10050],cnt;
void add(int u,int v,int w)
{
e[++cnt].nxt=head[u];
e[cnt].w=w;
e[cnt].to=v;
head[u]=cnt;
}
//深搜
bool vis[10050];
void dfs(int x)
{
vis[x]=true;
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v])continue;
dep[v]=dep[x]+1;
fa[v][0]=x;
f[v][0]=e[i].w;
dfs(v);
}
return ;
}
//lca
int lca(int x,int y)
{
if(find(x)!=find(y))return -1;
int ans=100000000;
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y])
{
ans=min(ans,f[x][lg[dep[x]-dep[y]]-1]);
x=fa[x][lg[dep[x]-dep[y]]-1];
}
if(x==y)return ans;
for(int k=lg[dep[x]]-1;k>=0;k--)
{
if(fa[x][k]!=fa[y][k])
{
ans=min(ans,min(f[x][k],f[y][k]));
x=fa[x][k],y=fa[y][k];
}
}
return ans=min(ans,min(f[x][0],f[y][0]));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&pe[i].u,&pe[i].v,&pe[i].w);
}
//kruskal
for(int i=1;i<=n;i++)pfa[i]=i;
sort(pe+1,pe+1+m,cmp);
for(int i=1;i<=m;i++)
{
int eu=find(pe[i].u),ev=find(pe[i].v);
if(eu==ev)continue;
pfa[ev]=eu;
add(pe[i].u,pe[i].v,pe[i].w);
add(pe[i].v,pe[i].u,pe[i].w);
}
//优化
for(int i=1;i<=n;i++)
{
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}
//对新建树深搜
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
fa[i][0]=i;
f[i][0]=100000000;
dep[i]=1;
dfs(i);
}
for(int i=1;i<=20;i++)
{
for(int j=1;j<=n;j++)
{
fa[j][i]=fa[fa[j][i-1]][i-1];
f[j][i]=min(f[j][i-1],f[fa[j][i-1]][i-1]);
}
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}