首页 > 代码库 > 最小生成树模板+并查集(隐藏)+结构体排序模板
最小生成树模板+并查集(隐藏)+结构体排序模板
minn[101],g[101][101],u[101]; memset(u,1,sizeof(u)); memset(minn,0x7f,sizeof(minn)); minn[1]=0; u[1]=0; i,j,k,m; total=0; for(i=1;i<=n;i++) { k=0; for(j=1;j<=n;j++) if(u[j]&&(minn[k]>minn[j])) k=j; u[k]=0; for(j=1;j<=n;j++) if(u[j]&&(g[k][j]<minn[j])) minn[j]=g[k][j]; } for(i=1;i<=n;i++) total+=minn[i]; cout<<total<<endl; /*prim*/ struct edge { int x,y,v; }a[1001]; int f[1001]; int find(int x) { if(find(x)==x)return x; f[x]=find(x); return f[x]; } unionn(int x,int y) { int fa=find(x); int fb=find(y); if(fa!=fb) f[fa]=fb; } int cmp(const edge &a,const edge &b) { if(a.v <b.v) return 1; else return 0; } //输入: cin>>n>>m; for(i=1;i<=m;i++) { cin>>fron>>to>>w; a[i].x=from; a[i].y=to; a[i].v=w; } //或者别的什么方式 //排序 sort(a,a+m+1); //核心代码 int sum=0,k=0; for(i=1;i<=m;i++) { int r1=find(a[i].x); int r2= find(a[i].y); if(r1!=r2) { sum+=a[i].v; k++; unionn(a[i].x,a[i].y); } if(k==n-1) break; } //输出 cout<<sum; /*Kruskal+并查集(隐)+结构体排序*/
我爱我自己!!!
最小生成树模板+并查集(隐藏)+结构体排序模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。