欢迎使用CSDN-markdown编辑器

2019-11-08 03:07:26

字体：大中小

来源：转载

供稿：网友

最小生成树算法模板包含Kruskal和PRim模板

#include <iostream>#include<bits/stdc++.h>using namespace std;#define maxn 2999//kruskal 算法贪心的求出最小生成树struct node{ int u,v,w;};//为了方便排序，建立一个结构体来存储边的关系node e[maxn];int n,m,sum=0,num=0,f[maxn+3];//f[]为并查集数组//快排原函数void quicksort(int left,int right){ int i,j; if(left>right) return; i = left; j = right; while(i!=j) { while(e[j].w>=e[left].w&&i<j) { j--; }//先从右边找到一个比基准数小的 while(e[i].w<+e[left].w&&i<j) { i++; } if(i<j) { swap(e[i],e[j]); } } swap(e[i],e[left]); quicksort(left,i-1); quicksort(i+1,right); return ;}int getf(int t)//递归找爹函数{ if(f[t]==t) return t; else { f[t] = getf(f[t]);//途中路径压缩 return f[t]; }}int amerge(int v,int u)//并查集合并子集函数，此处增加了判断两个点是否在同一个集合的功能{ int t1 = getf(v); int t2 = getf(u); if(t1!=t2) { f[t2] = t1; return 1; } return 0;}//在判断此边是否联通时，假如尚未联通则联通此边，直到满足cout == n-1即选用了N-1条边为止//排序算法借鉴了贪心思想int main(){int i;while(~scanf("%d%d",&n,&m)){ for(i=1;i<=m;i++)//依次读入各边 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); quicksort(1,m);//按照边长（权值）依次排序 for(i=1;i<=n;i++) { f[i] = i; } num = 0,sum = 0; //核心部分 for(i=1;i<=m;i++) { if(amerge(e[i].u,e[i].v))//如果两个顶点尚未联通，则选用这条边 { num++; sum+=e[i].w; } if(num==n-1) { break; } } printf("%d/n",sum);}return 0;}

模板2：

#include <iostream>#include<bits/stdc++.h>using namespace std;#define inf 99999999#define maxn 2002//Prim算法模板int e[maxn][maxn],book[maxn],dis[maxn],n,m,t1,t2,t3;int main(){ while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) e[i][j]=0; else e[i][j]= inf; } } for(int i=1;i<=m;i++) { scanf("%d%d%d",&t1,&t2,&t3); e[t1][t2] = t3; e[t2][t1] = t3; } for(int i=1;i<=n;i++) { book[i] = 0; dis[i] = e[1][i]; } int count = 0,sum = 0,min,j; book[1] = 1;//标记该点是否已经在生成树中 count++; while(count<n) { min = inf; for(int i=1;i<=n;i++) { if(book[i]==0&&dis[i]<min) { min = dis[i]; j = i; } }//从数组dis中找到离生成树最近的顶点，并加入生成树中 book[j] = 1; count++; sum+=dis[j];//数组dis表示生成树到各个顶点的距离 for(int k=1;k<=n;k++)//以J为中间点，更新生成树到每一个顶点的距离 { if(book[k]==0&&dis[k]>e[j][k]) dis[k] = e[j][k];//此处的松弛操作更改的是中间点到每个点（假如从该点到其他顶点更小的话则更新） } } //由于该算法是层层递推覆盖所以会取得最佳效果 printf("%d/n",sum); } return 0;}

上一篇：UVA 679 Dropping Balls (二叉树的编号)

下一篇：bzoj1051：受欢迎的牛（tarjan）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注