HDU1301 Jungle Roads(克鲁斯卡尔算法版)-阿里云开发者社区

开发者社区> 嗯哼9925> 正文

HDU1301 Jungle Roads(克鲁斯卡尔算法版)

简介:
+关注继续查看
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1301

通过对数组构造一个静态链表,将在同一个连通分量中的顶点链接起来。对按边权值从大到小排序后的边集合逐条进行判断,若边的起点和终点分别在不同的连通分量链表中(这通过获取其所在链表的表尾元素是否是同一个来进行判定),则此边加入最小生成树的边集合中,并将边的终点加入到边的起点所在的静态链表中。最终所有结点都会链接到一个静态链表中。

复制代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std ;

const int MAX_VETEXT_NUM = 26;//最大的顶点数
const int MAX_EDGE_NUM = 75;//最大的边数

struct Edge
{
    int begin;//起点
    int end;//结点
    double cost;//边的权值
};

Edge edge[MAX_EDGE_NUM];//边集合
double sum = 0;
int ConnectedList[MAX_VETEXT_NUM];//连通分量静态链表
int nEdges; //边的数目
int nVetexs; //顶点数目

int FindInConnectList( int Point[] , int v)
{//若v所在的连通分量静态链表为空,则返回参数v,否则返回其所在链表的表尾元素,
    int i = v ;
    while ( Point[i] > 0 ) 
        i = Point[i];
    return i ;
}

bool cmp( const Edge& a , const Edge& b )
{//根据边权值从小到大排序
    return a.cost < b.cost ;
}

void Kruscal()
{
    int i , j ; 
    int v1 , v2 ;
    //初始化连通分量静态链表
    for ( i = 0 ; i < nVetexs ; i++ )
    {
        ConnectedList[i] = 0 ;
    }
    i = 0 ; j = 0 ; 
    while ( j < nVetexs - 1 && i < nEdges )
    {
        v1 = FindInConnectList( ConnectedList , edge[i].begin) ;
        v2 = FindInConnectList( ConnectedList , edge[i].end) ;

        if ( v1 != v2)
        {//起点和终点不在同一个连通分量重
            sum += edge[i].cost;
            ConnectedList[v1] = v2 ;//加入连通分量链表中
            ++j;//最小生成树边数加1
        }
        ++i;//处理完一条边
    }
}

int main()
{
    int i , j ;
    int num ;
    double cost ;
    char chStart , chEnd;
    while ( cin >> nVetexs && nVetexs != 0)
    {
        sum = 0 ; 
        nEdges = 0 ;
        for ( i = 0 ; i < nVetexs - 1 ; i ++ )
        {
            cin >> chStart >> num ;
            for( j = 0 ; j < num ; j ++ )
            {
                cin >> chEnd >> cost ;
                edge[nEdges].begin = chStart - 'A' ;
                edge[nEdges].end = chEnd - 'A' ;
                edge[nEdges].cost = cost ;
                nEdges ++;
            }
        }
        sort(edge , edge + nEdges, cmp) ;
        Kruscal() ;
        cout << sum << endl ;   
    }
    return 0 ; 
}
复制代码



本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2009/09/13/1566016.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
7684 0
hdu4292Food(最大流Dinic算法)
/*    题意:每一个人都有喜欢的吃的和喝的,每一个人只选择一个数量的吃的和一个数量的喝的,问能满足最多的人数!?    思路:建图很是重要!f-food, p-people, d-drink    建图: 0(源点)--->f--->p---->p'---->d--->t(汇点) ...
650 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2594 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
9387 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
11020 0
阿里巴巴达摩院夺得首届“马栏山杯”国际音视频算法优化大赛【画质损伤修复赛道】冠军
首届“马栏山杯”国际音视频算法优化大赛颁奖盛典暨高峰论坛于9月8日举行。这场由中国工业与应用数学学会、中国网络社会组织联合会作为指导单位,湖南省互联网信息办公室、湖南省科学技术协会主办,中国(长沙)马栏山视频文创产业园、芒果TV承办的算法盛事,云集了全球优秀的算法精英。一大批来自高校、科研院所、互联网企业才子才女们,共1294支队伍报名参赛,其中北京大学34支,清华大学25支,麻省理工学院等国外顶级名校37支。
502 0
如何看待「机器学习不需要数学,很多算法封装好了,调个包就行」这种说法?
既然学术是自由的,我们就打开大门,欢迎大家都进来坐坐。如果他 / 她不喜欢,欢迎到隔壁串门。但我们不要给自己家门垒了高高的台阶,说闲人勿进。久而久之,难免门可罗雀。
815 0
+关注
4716
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载