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,如需转载请自行联系原作者
目录
相关文章
|
9月前
|
监控 算法
转:克鲁斯卡尔算法在文档管理软件中应用使其更加高效
克鲁斯卡尔算法是一种用于解决最小生成树问题的贪心算法。在文档管理软件中,可以将网络节点之间的连接关系抽象为一张图,然后使用克鲁斯卡尔算法来寻找最小生成树,即最小的连接所有节点的路径。
68 0
|
10月前
|
存储 算法 搜索推荐
克鲁斯卡尔算法
克鲁斯卡尔算法
|
10月前
|
存储 算法 数据可视化
转:电子文档管理系统中应用克鲁斯卡尔算法有什么作用
克鲁斯卡尔算法是一种求解最小生成树问题的算法,其在电子文档管理系统中可以用于优化文档的管理和存储。
50 0
|
算法 C++
蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树
蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树
71 0
|
存储 算法 数据可视化
转:克鲁斯卡尔算法在电子文档管理系统中的应用
克鲁斯卡尔算法能够找到连接所有节点的最小生成树,从而找到最优解。在电子文档管理系统中,这意味着可以通过算法找到最佳的文档组织方式,提高文档检索的效率和精度。
289 0
|
监控 算法
转:克鲁斯卡尔算法在电脑监控软件中的应用
在电脑监控软件中,使用克鲁斯卡尔算法可以帮助管理员更好地了解整个网络的拓扑结构,找出网络中潜在的问题和风险点。
303 0
|
算法
Kruskal算法(克鲁斯卡尔)最小生成树
Kruskal算法(克鲁斯卡尔)最小生成树
109 0
|
15天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
1天前
|
算法 数据安全/隐私保护 C++
基于二维CS-SCHT变换和扩频方法的彩色图像水印嵌入和提取算法matlab仿真
该内容是关于一个图像水印算法的描述。在MATLAB2022a中运行,算法包括水印的嵌入和提取。首先,RGB图像转换为YUV格式,然后水印通过特定规则嵌入到Y分量中,并经过Arnold置乱增强安全性。水印提取时,经过逆过程恢复,使用了二维CS-SCHT变换和噪声对比度(NC)计算来评估水印的鲁棒性。代码中展示了从RGB到YUV的转换、水印嵌入、JPEG压缩攻击模拟以及水印提取的步骤。
|
2天前
|
机器学习/深度学习 算法 数据可视化
基于BP神经网络的32QAM解调算法matlab性能仿真
```markdown - 32QAM解调算法运用BP神经网络在matlab2022a中实现,适应复杂通信环境。 - 网络结构含输入、隐藏和输出层,利用梯度下降法优化,以交叉熵损失最小化为目标训练。 - 训练后,解调通过前向传播完成,提高在噪声和干扰中的数据恢复能力。 ``` 请注意,由于字符限制,部分详细信息(如具体图示和详细步骤)未能在摘要中包含。