（洛谷 3366）【模（mú）板】最小生成树#kruskal,并查集#

2019-04-13 22:06发布

站内文章 / 模拟电子
16280 0 1161
class="markdown_views prism-atom-one-light">

分析

Kruskal来一波

代码

#include #include using namespace std; struct uni{ int u,v,w; }e[200001],t; int n,p=1,m,ans,f[200001]; bool cmp(uni x,uni y){return (x.w<y.w)||((x.w==y.w)&&(x.u>y.u));} int father(int yu){if (f[yu]==yu) return yu; return f[yu]=father(f[yu]);} void qsort(int l,int r){ int i=l,j=r;uni mid=e[(i+j+1)>>1]; while(i<=j){ while(cmp(e[i],mid))i++; while(cmp(mid,e[j]))j--; if(i<=j){ t=e[i];e[i]=e[j];e[j]=t; i++;j--; } } if(l<j)qsort(l,j); if(i<r)qsort(i,r); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) f[i]=i; for (int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); qsort(1,m); for (int i=1;i<=m;i++) if (father(e[i].u)!=father(e[i].v)){ //祖先不同 f[father(e[i].v)]=e[i].u;//合并祖先 ans+=e[i].w;//加入最小生成树 p++; if (p==n) break;//最多连n-1条边 } printf("%d",ans); return 0; }

热门文章