/*
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
19
*/
*/
#include<stdio.h>
struct edge{
int u;
int v;
int w;
} e[10];
int n,m;
int f[7]={0},sum=0,count=0;
void quicksort(int left,int right)
{
int i,j;
struct edge t;
if(left > right)
return ;
i=left;
j=right;
while(i!=j)
{
while(e[j].w>=e[left].w && i<j)
j--;
while(e[i].w<=e[left].w && i<j)
i++;
if(i<j)
{
t=e[i];
e[i]=e[j];
e[j]=t;
}
}
t=e[left];
e[left]=e[i];
e[i]=t;
quicksort(left,i-1);
quicksort(i+1,right);
return ;
}
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
int join(int u,int v)
{
int x=find(u);
int y=find(v);
if(x!=y)
{
f[y]=x;
return 1;
}
return 0;
}
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
quicksort(1,m);
/*
for(i=1;i<=m;i++)
printf("%d-",e[i].w);*/
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)
{
if(join(e[i].u,e[i].v))
{
count++;
sum+=e[i].w;
}
if(count==n-1)
break;
}
printf("%d\n",sum);
return 0;
}
krustra算法是加边法，每次把权值最小的边加入到集合S中（每次需要判断这条边的两个顶点连通不连通，如果不连通加入集合），直到集合S==n-1；
转载请注明原文地址: https://ju.6miu.com/read-671630.html
