最小生成树总结
模板
kruskal（O(mlogm)）
每次找最小边，只要没有产生回路就冲！
ll kru(ll st){
ll ma=0;
ll mi=1e18;
ll cnt=0;
ll ans=0;
for(int i=st;i<=m;i++){
ll ru=sr[i].x;
ll rv=sr[i].y;
if(find(ru)!=find(rv)){//没有回路
ad(ru,rv);
ans+=sr[i].z;
cnt++;
}
if(cnt==n-1){
return ans;
}
}
return -1;
}
注：并查集 find 一定这样写：return fa[x]=find(fa[x]);
prim(O(nm))
每次看已经收入的点，找到一个最小的边，再跑
wait
例题
道路修建