并查集和最小生成数，求帮助

Question

#include
typedef struct edge
{
int u;
int v;
int w;
}edge;
edge e[10];
int n,m;
int f[7] = {0},sum = 0,count = 0;

void quicksort(int left,int right)
{
int i,j;
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;
}
}
//将基准数归位 （放到最后应该在的位置）,将left的和i互换m；
t = e[left];
e[left] = e[i];
e[i] = t;
quicksort(left,i-1);
quicksort(i+1,right);
return;
}
int getf(int v)
{
if(f[v] == v)
return v;
else
{
f[v] = getf(f[v]);
return f[v];
}
}

int merge(int u,int v)
{
int t1,t2;
t1 = getf(u);
t2 = getf(v);
if(t1 != t2);//判断两个节点是否在同一个集合中 ，即是否为同一个祖先
{
f[t2] = t1;
return 1;
//靠左原则，左边的变成右边的boss
}
return 0;
}

int main ()
{
int i,j;
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 <= n;i++)
f[i]= i;
for(i = 1;i <= m;i++)
{
if(merge(e[i].u,e[i].v) > 0)
{
count++;
sum += e[i].w;
printf("%d %d\n",e[i].u,e[i].v);

        for(j = 1;j <= 6;j++)
            printf("%d ",f[j]);
        printf("\n");

    }
    if(count == n-1)
        break;
} 
printf("%d",sum);
return 0;

}

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
这个程序输出结果是16

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 关于该问题，我找了一篇非常好的博客，你可以看看是否有帮助，链接：图论 —— 生成树 —— 最小瓶颈生成树

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 以帮助更多的人 ^-^