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,如需转载请自行联系原作者
目录
相关文章
|
10月前
|
监控 算法
转:克鲁斯卡尔算法在文档管理软件中应用使其更加高效
克鲁斯卡尔算法是一种用于解决最小生成树问题的贪心算法。在文档管理软件中,可以将网络节点之间的连接关系抽象为一张图,然后使用克鲁斯卡尔算法来寻找最小生成树,即最小的连接所有节点的路径。
71 0
|
11月前
|
存储 算法 搜索推荐
克鲁斯卡尔算法
克鲁斯卡尔算法
|
11月前
|
存储 算法 数据可视化
转:电子文档管理系统中应用克鲁斯卡尔算法有什么作用
克鲁斯卡尔算法是一种求解最小生成树问题的算法,其在电子文档管理系统中可以用于优化文档的管理和存储。
53 0
|
存储 算法 数据可视化
转:克鲁斯卡尔算法在电子文档管理系统中的应用
克鲁斯卡尔算法能够找到连接所有节点的最小生成树,从而找到最优解。在电子文档管理系统中,这意味着可以通过算法找到最佳的文档组织方式,提高文档检索的效率和精度。
290 0
|
算法 C++
蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树
蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树
74 0
|
监控 算法
转:克鲁斯卡尔算法在电脑监控软件中的应用
在电脑监控软件中,使用克鲁斯卡尔算法可以帮助管理员更好地了解整个网络的拓扑结构,找出网络中潜在的问题和风险点。
305 0
|
算法
Kruskal算法(克鲁斯卡尔)最小生成树
Kruskal算法(克鲁斯卡尔)最小生成树
111 0
|
1天前
|
机器学习/深度学习 算法
基于鲸鱼优化的knn分类特征选择算法matlab仿真
**基于WOA的KNN特征选择算法摘要** 该研究提出了一种融合鲸鱼优化算法(WOA)与K近邻(KNN)分类器的特征选择方法,旨在提升KNN的分类精度。在MATLAB2022a中实现,WOA负责优化特征子集,通过模拟鲸鱼捕食行为的螺旋式和包围策略搜索最佳特征。KNN则用于评估特征子集的性能。算法流程包括WOA参数初始化、特征二进制编码、适应度函数定义(以分类准确率为基准)、WOA迭代搜索及最优解输出。该方法有效地结合了启发式搜索与机器学习,优化特征选择,提高分类性能。
|
1天前
|
机器学习/深度学习 算法 数据可视化
基于BP神经网络的64QAM解调算法matlab性能仿真
**算法预览图省略** MATLAB 2022A版中,运用BP神经网络进行64QAM解调。64QAM通过6比特映射至64复数符号,提高数据速率。BP网络作为非线性解调器,学习失真信号到比特的映射,对抗信道噪声和多径效应。网络在处理非线性失真和复杂情况时展现高适应性和鲁棒性。核心代码部分未显示。
|
4天前
|
机器学习/深度学习 算法 数据可视化
m基于PSO-LSTM粒子群优化长短记忆网络的电力负荷数据预测算法matlab仿真
在MATLAB 2022a中,应用PSO优化的LSTM模型提升了电力负荷预测效果。优化前预测波动大,优化后预测更稳定。PSO借鉴群体智能,寻找LSTM超参数(如学习率、隐藏层大小)的最优组合,以最小化误差。LSTM通过门控机制处理序列数据。代码显示了模型训练、预测及误差可视化过程。经过优化,模型性能得到改善。
19 6