蒟蒻调晕了
查看原帖
蒟蒻调晕了
105266
kakao楼主2020/11/30 11:08

怎么调都不对,求大佬帮看以下,感觉自己写的还是很清晰的(哭)

#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;
}
2020/11/30 11:08
加载中...