标题:大佬们帮忙看一下那个环节出了问题了 感谢
只看楼主
风流泰
Rank: 1
等 级:新手上路
帖 子:78
专家分:0
注 册:2018-9-29
结帖率:87.88%
已结贴  问题点数:20 回复次数:3 
大佬们帮忙看一下那个环节出了问题了 感谢
//镖局运镖-图的最小生成树
#include<stdio.h>
struct edge
{
    int u;
    int v;
    int w;
}; //为了方便,这里创建了一个结构体用来储存边的关系
struct edge e[10];//数组大小根据实际情况来设置,要比m的值大1
int n,m;
int f[7]={0},sum=0,count=0;//并查集需要用到的一些变量
//f数组根据实际情况来设置,要比n的最大值大1
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;
   
    //最终将基准数归位,将left和i交换
    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 v,int u)
{
    int t1,t2;
    t1=getf(v);
    t2=getf(u);
    if(t1!=t2)
        f[t2]=t1;
        return 1;
    return 0;
}

//请从此处开始阅读程序,从主函数开始阅读程序是一个好习惯
int main(void)
{
    int i;
    //读入n和m,n表示顶点个数,m表示边的条数
    scnaf("%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;
   
    //kruskal算法核心部分
    for(i=1;i<=m;i++) //开始从小到大枚举每一条边
        //判断一条边的两个顶点是否已经连通,既判断是否已在同一个集合中
        if(merge(e[i].u,e[i].v))
            count++;
            sum+=e[i].w;
            
        if(count==n-1)//指导选用了n-1条边之后退出循环
             break;
            
    printf("%d\n",sum);//打印结果
    getchar();getchar();
    return 0;
}

/*错误提示 :    [Error] break statement not within loop or switch*/
搜索更多相关主题的帖子: int sum left return i++ 
2019-03-19 15:21
grmmylbs
Rank: 14Rank: 14Rank: 14Rank: 14
等 级:贵宾
威 望:54
帖 子:1409
专家分:5845
注 册:2016-2-14
得分:10 
不爱用括号的结果
2019-03-19 16:29
WatchCurtai
Rank: 2
等 级:论坛游民
帖 子:5
专家分:38
注 册:2018-10-24
得分:10 
小白一只,不懂
2019-03-19 17:09
风流泰
Rank: 1
等 级:新手上路
帖 子:78
专家分:0
注 册:2018-9-29
得分:0 
回复 2楼 grmmylbs
哦 原来如此
2019-03-20 15:43



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-493686-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.236090 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved