[code=Cpp width=740px]//Kruskal
#include <stdio.h>
struct node
{
int x,y,len;
}e[1000];
int f[100]={0},n,m,k,sum;
int cmp(const void *x,const void *y)
{
return (*(struct node *)x).len-(*(struct node *)y).len;
}
//这是找爹的递归函数,不停的去找爹,只到找到祖宗为止
int getf(int v)
{
if(f[v]==v)
return v;
else
{
//这里是路径压缩,每次在函数返回的时候,顺带把路上遇到的人的祖宗都改为最后找到的祖宗的编号
f[v]=getf(f[v]);
return f[v];
}
}
//这里是合并两子集合的函数,如果需要判断的两个节点,在不同的集合中
//我们就把右边的集合,作为左边集合的子集合,
void merge(int v,int u)
{
int t1,t2;
t1=getf(v);
t2=getf(u);
if( t1!=t2 )
{
f[t1]=t2;//经过路径压缩以后,将f的根的值也赋值为v的祖先f[t1]
}
}
//判断连个点是否在一个集合中,不多说了,你懂的
int query(int v,int u)
{
if(getf(v)==getf(u))
return 1;
else
return 0;
}
//请从此处开始阅读程序,从主函数开始阅读程序是一个好习惯
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int i,x,y;
scanf("%d %d",&n,&m);
for(i=1;i <= m;i++)
{
scanf("%d %d %d", &e.x, &e.y, &e.len);
}
qsort(&e[1],m,sizeof(e[0]),cmp);
for(i=1;i <= m;i++)
printf("%d %d %d\n",e.x,e.y,e.len);
printf("---\n");
//初始化是必须的
for(i=1;i <= n;i++)
f=i;
i=1;k=0;sum=0;
while(k < n)
{
if( query(e.x,e.y)==0 )
{
k++;
sum += e.len;
//开始集合的合并处理
merge(e.x,e.y);
}
i++;
}
printf("%d",sum);
return 0;
}
[/code]
|