在用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),只有第一种(x,y,w)可以AC,链式前向星取回WA几个点,但大部分AC。想了很久不理解,为什么会怎样?