歡迎使用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）