Kruskal 相对而言快了很多,用并查集实现
我写了俩个,不过效率相差太大了
Kruskal算法 #include<iostream>#include<string>#define MAXN 101using namespace std;int n,m,f[MAXN],ans;struct edge{int u,v,w; edge(int x=0,int y=0,int z=0):u(x),v(y),w(z){};}e[MAXN*50];int cmp(const void *a, const void *b) { if(((struct edge *)a)->w!=((struct edge *)b)->w) {return ((struct edge *)a)->w-((struct edge *)b)->w; }else {return ((struct edge *)a)->u-((struct edge *)b)->u; }} void init(){for(int i=0;i<=n;i++) f[i]=i;}int find(int x){if(x==f[x])return x; f[x]=find(f[x]);return f[x];}void Union(int x,int y,int c){int a=find(x);int b=find(y);if(a==b)return ; f[b]=a; ans+=c;}int main(){int a,b,c;while(scanf("%d",&n)==1&&n) { m=(n*(n-1))/2;int num=0;for(int i=0;i<m;i++) { scanf("%d %d %d",&a,&b,&c); e[num++]=edge(a,b,c); } qsort(e,num,sizeof(e[0]),cmp); init(); ans=0;for(int i=0;i<num;i++) Union(e[i].u,e[i].v,e[i].w); printf("%d\n",ans); }return 0;}
转载于:https://www.cnblogs.com/nanke/archive/2011/08/15/2139999.html
相关资源:数据结构—成绩单生成器