#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include <algorithm>
using namespace std;
/*
typedef struct node
{
int a;
int b;
int number;
int length;
};
node [100];*/
int p[5002];
int u[100],v[100],w[100];
int cmp(const int i,const int j)
{
return w[i]<w[j];
}
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
int kruskal(int u[],int v[],int w[],int n)
{
int ans=0;
int r[100];
for(int i=0;i<n*(n-1)/2;i++)p[i]=i;
for(int i=0;i<n*(n-1)/2;i++)r[i]=i;
sort(r,r+n*(n-1)/2,cmp);
for(int i=0;i<n*(n-1)/2;i++)
{
int e=r[i];
int x=find(u[e]);
int y= find(v[e]);
if(x!=y){ans+=w[e];p[x]=y;}
}
return ans;
}
int main() //妹的、、ac不了、、气死了、、第一棵树、、
{
int n,i;
int min;
while(scanf("%d",&n)&&n)
{
memset(p,0,sizeof(p));
for(i=0;i<n*(n-1)/2;i++)
scanf("%d %d %d",&u[i],&v[i],&w[i]);
min=kruskal(u,v,w,n);
printf("%d\n",min);
}
system("pause");
return 0;
}
别人的、、
#include <stdio.h>
#include<stdlib.h>
#include <algorithm>
using namespace std;
struct node
{ int x,y;
int z;
}shu[50000];
int p[50000];
int findx(int x)
{/*
int r;
r=x;
while(r!=p[r])
{
r=p[r];
}
p[r]=r;
return r;*/
if(x==p[x])
return x;
p[x]=findx(p[x]);
return p[x];
}
int connect(int x,int y)
{
int q,w;
q=findx(x);
w=findx(y);
/*
if(q!=w)
{
if(q>w)
{p[q]=w;}
else {p[w]=q;}
return 1;
}
else return 0;*/
if(q==w)
return 0;
p[w]=q;
return 1;
}
/*
int cmp(const void *aa,const void*bb)
{
return((*(struct node*)aa).z-(*(struct node*)bb).z);
}*/
int cmp(node a,node b)
{
return a.z<b.z;
}
int main()
{
// freopen("in.txt","r",stdin);
int n,t,i,sum,m;
while(scanf("%d",&n)&&n)
{
t=(n-1)*n/2;
for(i=0;i<=t;i++)
p[i]=i;
for(i=0;i<t;i++)
{
scanf("%d%d%d",&shu[i].x,&shu[i].y,&shu[i].z);
}
//qsort(shu,t+1,sizeof(shu[0]),cmp);
sort(shu,shu+t,cmp);
sum=0;
m=1;
for(i=0;i<t;i++) {
if(connect(shu[i].x,shu[i].y)){m++;sum+=shu[i].z;}
}
printf("%d\n",sum);
}
return 0;}
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
