prim和kruskal(最小生成树)(kruskal模板)
题目: P3366 【模板】最小生成树
n为点,m为边
prim: O(nlgn) //以边遍历点,因其一边有两个点,所以每个点会有两次判断,所以复杂度为n^2,通过堆优化可以变成 nlgn prim是从一个点散出去找与其相连的未被访问的最小边 所以要用前向星的add kruskal: O(mlgm) //复杂度主要是为边排序 //n小就用prim //m小就用kruskal kruskal是从全局找未被访问的最小边 所以只要边排序就够了,用不到add 前向星:没有add函数的node不是前向星 通过前向星可以访问到与i相连点和边
以下是kruskal
#include<bits/stdc++.h> using namespace std; int const N=5e3+7; int const M=2e5+7; int n,m; struct node{ int a,next,len; }e[M]; bool cmp(node a,node b){ return a.len < b.len ; } int f[N]; int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void merge(int x,int y){ f[find(x)]=find(y); } void kruskal(){ int cnt=0,sum=0,flag=0; sort(e+1,e+m+1,cmp); for(int i=1;i<=n;++i) f[i]=i; for(int i=1;i<=m;++i){ int a=e[i].a , b=e[i].next ; if(find(a)!=find(b)){ merge(a,b); cnt++; sum+=e[i].len ; if(cnt>=n-1) { flag=1;break; } } } if(flag) cout << sum; else cout << "orz"; } int main(){ cin >> n >> m; for(int i=1;i<=m;++i){ cin >> e[i].a >> e[i].next >> e[i].len ; } kruskal(); //克鲁斯卡尔 return 0; }