首页 > 代码库 > 【kruscal】【最小生成树】bzoj2421 Constructing Roads
【kruscal】【最小生成树】bzoj2421 Constructing Roads
SB题,求最小生成树,其中有些边已经给您建好啦。
随意暴力即可。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int rank[10001],fa[10001],n,m,a[101][101],q,x,y,f1,f2,ans; 6 void init(){for(int i=1;i<=n;i++) fa[i]=i;} 7 int findroot(int x) 8 { 9 if(fa[x]==x) return x;10 int rt=findroot(fa[x]);11 fa[x]=rt;12 return rt;13 }14 void Union(int U,int V)15 {16 if(rank[U]<rank[V]) fa[U]=V;17 else18 {19 fa[V]=U;20 if(rank[U]==rank[V]) rank[U]++;21 }22 }23 struct Edge{int u,v,w;Edge(const int &a,const int &b,const int &c){u=a;v=b;w=c;}Edge(){}};24 bool cmp(const Edge &a,const Edge &b){return a.w<b.w;}25 Edge edges[10001];26 int main()27 {28 scanf("%d",&n);29 for(int i=1;i<=n;i++)30 for(int j=1;j<=n;j++)31 scanf("%d",&a[i][j]);32 for(int i=1;i<=n;i++)33 for(int j=i+1;j<=n;j++)34 edges[++m]=Edge(i,j,a[i][j]);35 sort(edges+1,edges+m+1,cmp);36 scanf("%d",&q);37 init();38 for(int i=1;i<=q;i++)39 {40 scanf("%d%d",&x,&y);41 f1=findroot(x); f2=findroot(y);42 if(f1!=f2) Union(f1,f2);43 }44 for(int i=1;i<=m;i++)45 {46 f1=findroot(edges[i].u); f2=findroot(edges[i].v);47 if(f1!=f2)48 {49 Union(f1,f2);50 ans+=edges[i].w;51 }52 }53 printf("%d\n",ans);54 return 0;55 }
【kruscal】【最小生成树】bzoj2421 Constructing Roads
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。