关于Kruskal的疑问
查看原帖
关于Kruskal的疑问
255077
麦克斯韦の妖楼主2021/10/16 13:54

在用Kruskal求最小生成树时,有两种存图的方法:

struct Node{
	int x,y,w;
}edge[N*N]; //x,y为边上的两点

struct Node{
	int to,next,w;
}edge[N*N]; //链式前向星

在Kruskal中,分别

sort(edge,edge+tot,cmp);
for(int i=0;i<tot;i++){
	int v=edge[i].x;
	int u=edge[i].y;
	if(Find(u)!=Find(v)){
		ans+=edge[i].w;
		Union(u,v);
	}
}

sort(edge,edge+tot,cmp);
for(int i=0;i<tot;i++){
	int v=edge[i].to;
	int u=edge[i^1].to;
	if(Find(u)!=Find(v)){
		ans=edge[i].w+ans;
		Union(u,v);
	}
}

两种都可以通过模板。 但在一些题中(如P1194),只有第一种(xyw)(x,y,w)可以AC,链式前向星取回WA几个点,但大部分AC。想了很久不理解,为什么会怎样?

2021/10/16 13:54
加载中...