实在找不出是哪里错了,求助。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXN 10010
#define INF 0x7fffffff
int n,m,x,y,q1,u,v,l;
struct node{
int x,y,z;
}a[50010];
struct point{
int y,z,next;
}edge[100010];
int cmp(const node &a,const node &b)
{
return a.z>b.z;
}
bool vis[MAXN];
typedef int arr[MAXN];
arr deep,head,father;
int f[MAXN][30],g[MAXN][30];

int find(int x)
{
if (father[x]==x) return x;
return father[x]=find(father[x]);
}
void add(int x,int y,int z)
{
l++;
edge[l].y=y;
edge[l].z=z;
edge[l].next=head[x];
head[x]=l;
}
void kruscal()
{
for (int i=1;i<=n;i++) father[i]=i;
for (int i=1;i<=m;i++)
{
u=find(a[i].x);
v=find(a[i].y);
if (u!=v)
{
father[u]=v;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
}
}
}
void dfs(int x)
{
vis[x]=true;
int p=head[x];
while (~p)
{
if (!vis[edge[p].y])
{
deep[edge[p].y]=deep[x]+1;
f[edge[p].y][0]=x;
g[edge[p].y][0]=edge[p].z;
dfs(edge[p].y);
}
p=edge[p].next;
}
}
void prepare()
{
memset(vis,false,sizeof(vis));
for (int i=1;i<=n;i++)
if (!vis[i])
{
deep[i]=1;
dfs(i);
}
for (int j=15;j>=1;j--)
for (int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);
}
}
int lca(int x,int y)
{
if (deep[x]>deep[y])
{
int t=x;x=y;y=t;
}
int ans=INF;
for (int i=15;i>=0;i--)
if (deep[y]-deep[x]>=(1<<i))
{
ans=min(ans,g[y][i]);
y=f[y][i];
}
if (x==y) return ans;
for (int i=15;i>=0;i--)
if (f[x][i] && f[x][i]!=f[y][i])
{
ans=min(ans,g[x][i]);
ans=min(ans,g[y][i]);
x=f[x][i];
y=f[y][i];
}
ans=min(ans,min(g[x][0],g[y][0]));
return ans;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+m+1,cmp);
memset(head,-1,sizeof(head));
l=0;
kruscal();
prepare();
cin>>q1;
while (q1--)
{
cin>>x>>y;
if (find(x)!=find(y))
{
cout<<"-1"<<endl;
continue;
}
else
cout<<lca(x,y)<<endl;
}
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1843
难度
7
分类
(无)
标签
递交数
5319
已通过
954
通过率
18%
被复制
10
上传者