最小生成树

kruskal

int get(int x) { if(x==fa[x]) return fa[x]; return fa[x]=get(fa[x]); } sort(e+1,e+m+1); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int x=get(e[i].x); int y=get(e[i].y); if(x==y) continue; fa[x]=y; ans+=e[i].z; }

prim

void prim() { memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1;i<n;i++) { int x=0; for(itn j=1;j<=n;j++) { if(!v[j] && (x==0 || d[j]<d[x]))x=j; } v[x]=1; for(int y=1;y<=n;y++) { if(!v[y]) d[y]=min(d[y],a[x][y]); } } }