kruskal1.txt

kruskal算法求解最小生成树 K r u s k a l算法每次选择n- 1条边

#include<stdio.h> 
long i,j,k,m,n; 
long cost,treenum; 
long root[32001],rank[32001]; 
struct edge{ 
     long x; 
     long y; 
     long w; 
     }; 
struct edge e[100000]; 
long sort(long l,long r){ 
     long low=l,hi=r,mid=e[(l+r)/2].w,tmp; 
      do{ 
          while(e[low].w<mid)low++; 
          while(e[hi].w>mid)hi--; 
          if(low<=hi){ 
          tmp=e[low].x; e[low].x=e[hi].x; e[hi].x=tmp; 
          tmp=e[low].y; e[low].y=e[hi].y; e[hi].y=tmp; 
          tmp=e[low].w; e[low].w=e[hi].w; e[hi].w=tmp; 
          low++; hi--; 
          } 
       }
	while(low<=hi); 
   if(low<r) sort(low,r); 
   if(l<hi) sort(l,hi); 
   return 0;
} 
long init(){ 
            scanf("%ld%ld",&n,&m); 
            for(i=1;i<=m;i++) 
                  scanf("%ld%ld%ld",&e[i].x,&e[i].y,&e[i].w); 
                  sort(1,m); 
                 treenum=n; 
            return 0;
} 
long findset(long x){ 
if(root[x]!=x) 
root[x]=findset(root[x]); 
return root[x]; 
} 
long link(long a,long b){ 
             if(rank[a]>rank[b]) 
                root[b]=a; 
            else if(rank[a]<rank[b]) 
            root[a]=b; 
            else{ 
             root[a]=b; 
             rank[b]++; 
               } 
			return 0;
} 
long unite(long a,long b){ 
           link(findset(a),findset(b)); 
		   return 0;
} 
long work(){ 
       long x,y; 
       for(i=1;i<=n;i++) 
           root[i]=i; 
       for(i=1;treenum>1;i++){ 
           x=e[i].x; y=e[i].y; 
        if(findset(x)!=findset(y)){ 
            cost+=e[i].w; 
            unite(x,y); 
            treenum--; 
             } 
        } 
         printf("%ld\n",cost); 
		 return 0;
} 
 int main() 
{ freopen("hello.in","r",stdin); 
freopen("hello.out","w",stdout); 
init(); 
work(); 
return 0; 
}