【NOJ1596、1597】【贪心算法之最小生成树】最少修建多长的公路能把所有村庄连起来(图示Prim与Kruskal算法)

2018年10月6日 11点热度 0条评论 来源: 夏至夏至520

1596.最少修建多长的公路能把所有村庄连起来(一)

时限:1000ms 内存限制:10000K  总时限:3000ms

描述

一个地区有n个村庄,有一些村子之间可以修路,已知每条路的长度,问最少修建多长的公路可以把所有的村子连接起来。

输入

先输入两个正整数n,m(n小于10000,m小于100000),表示有n个村庄,m条可以修建的路,接下来的m行每行三个整数,前两个表示村庄的编号(0~n-1),第三个表示这条路的长度。

输出

输出路的总长度的最小值。

#include <iostream>
#include <climits>

using namespace std;

//本题选用Kruskal算法,因邻接矩阵顶点太多,边太少
//若用二维数组存放数据太浪费
//本题采用并查集判断两个顶点是否连通

int n,m;

int a[10000];    //并查集
int x[100000],y[100000],dis[100000];    //存放边
int isIn[100000];   //边是否已在集合中

int fsearch(int x);         //返回并查集中x节点的根节点
void a_add(int x, int y);   //将两个顶点连通
bool isUn(int x, int y);    //判断x和y两个顶点是否连通

int main()
{
    //Krustal算法+并查集

    //输入数据
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        cin>>x[i]>>y[i]>>dis[i];
    }

    //初始化
    for(int i=0; i<n; i++)
    {
        a[i]=i;
    }

    //将边按权值升序排列
    for(int i=0; i<m; i++)
    {
        for(int j=i; j<m; j++)
        {
            if(dis[j]<dis[i])
            {
                swap(dis[j],dis[i]);
                swap(y[j],y[i]);
                swap(x[j],x[i]);
            }
        }
    }

    //按升序遍历边,加入集合,共m条边
    int dist=0;
    for(int i=0; i<m; i++)
    {
        if(!isUn(x[i],y[i]))//若第i条边的两个顶点不连通
        {
            a_add(x[i],y[i]);   //将两个顶点连通
            dist+=dis[i];   //加入这条边的边长
        }
        else                //若已经连通则查看下一条边
        {
            continue;
        }
    }

    cout<<dist<<endl;
    return 0;
}

int fsearch(int x)   //返回并查集中x节点的根节点
{
    int f=a[x];
    while(f!=a[f])
    {
        f=a[f];
    }
    a[x]=f;
    return f;
}


void a_add(int x, int y)    //将两个顶点连通
{
    int kx=fsearch(x);
    int ky=fsearch(y);
    a[ky]=kx;
}

bool isUn(int x, int y)     //判断x和y两个顶点是否连通
{
    int kx=fsearch(x);
    int ky=fsearch(y);
    if(kx==ky)
    {
        return true;
    }
    else
    {
        return false;
    }
}

1597.最少修建多长的公路能把所有村庄连起来(二)

时限:1000ms 内存限制:10000K  总时限:3000ms

描述

一个地区有n个村庄,有一些村子之间可以修路,已知每条路的长度,问最少修建多长的公路可以把所有的村子连接起来。

输入

先输入一个正整数n(n小于500),表示有n个村庄,接下来n行每行n个正整数,其中第i行第j列的元素表示第i个村庄到第j个村庄之间的距离。

输出

输出路的总长度的最小值。

#include <iostream>
#include <climits>

using namespace std;

//本题选用Prim算法,因邻接矩阵不稀疏

int n,m;

int dist[500][500]; //邻接矩阵
int isIn[10000];    //节点是否在集合中
int f[10000];       //权值:每个节点到集合的距离

int mindist();   //返回当前离集合最近点的下标

int main()
{
    //Prim算法

    cin>>n;

    for(int i=0; i<n; i++)  //输入数据
    {
        for(int j=0; j<n; j++)
        {
            cin>>dist[i][j];
        }
    }

    //初始化isIn数组
    isIn[0]=1;  //将节点0加入集合
    for(int i=1; i<n; i++)
    {
        isIn[i]=0;
    }

    //初始化各节点权值
    for(int i=1; i<n; i++)
    {
        f[i]=dist[0][i];    //初始权值为到顶点i的距离
    }

    int dis=0;  //总距离
    for(int cnt=1; cnt<n; cnt++)    //每次for循环添加一个节点进集合
    {
        int x=mindist();   //返回离集合最近节点下标
        //cout<<x<<' '<<isIn[x]<<endl;
        isIn[x]=1;  //将该节点加入集合
        dis+=f[x];  //将权值加入总距离中
        //cout<<dis<<' ';

        for(int i=0; i<n; i++)  //更新各节点权值
        {
            if(!isIn[i])    //遍历不在集合中的节点
            {
                if(dist[x][i]<f[i])
                {
                    f[i]=dist[x][i];
                    //cout<<f[i]<<endl;
                }
            }
        }
    }

    cout<<dis<<endl;

    return 0;
}

int mindist()    //返回当前离集合最近点的下标
{
    int min_i=1;
    int min_dist=INT_MAX;
    for(int i=1; i<n; i++)
    {
        if(!isIn[i])
        {
           if(f[i]<min_dist)
            {
                min_dist=f[i];
                min_i=i;
            }
        }
    }
    return min_i;
}

【后记】

1.最小生成树问题,有两种算法,Prim算法与Krustal算法

当e=Ω(n²)时,Prim算法性能好

当e=o(n²)时,Krustal性能好

2.Prim算法将顶点分为两个集合A和B,集合A中最初只有顶点0,其余顶点都在集合B中

集合B中每个顶点都有一个权值 f,f [ i ] 定义为“顶点 i 到集合A的最短距离”,初始值为“顶点 i 到顶点0的最短距离”

若顶点 i 到顶点0没有连接边,那么 f [ i ] 的初始值为INT_MAX,即无穷大,需要#include <climits>

开始for循环,每次循环,从集合B中选取一个权值最小的顶点X加入集合A,相当于顶点X已经与集合A中的各顶点连通,然后更新集合B中剩下的顶点权值

更新意义在于:顶点X已经从集合B加入了集合A,那么如果集合B中有一个顶点Y到顶点X的距离比它到集合A的距离更短,就要把顶点Y的权值更新成它到顶点X的距离

当for循环次数等于顶点数-1时,每个顶点都被加入了集合A,意味着所有顶点都连通起来

Prim算法演示图(红色数字权值是每张图中加入新顶点前还没更新的权值)

 

3.Kruskal算法,先将各条边按照距离值从小到大排列

开始for循环,每次循环选取一条距离值最小的边,判断一下这条边两端的顶点A和顶点B是否连通

如果A和B不连通,就把它们连通起来,确定添加这条边

如果A和B连通,就删除这条边不添加(否则会形成回路),查看下一条边

当循环次数等于边数时,所有边都被查看了一遍,要么添加要么删除,最后所有顶点都连通起来,并且没有回路

Kruskal算法演示图

4.在Kruskal算法中,需要判断一条边的两个顶点是否连通,这里用到了并查集

并查集可以用一个数组a[]表示,a [ i ] = i 表示节点 i 为根节点

若一条边的顶点A和顶点B的根节点相同,说明两个顶点在一棵树上,即连通

若顶点A和顶点B的根节点不同,说明不连通,那么在Kruskal算法中需要让A和B连通,此时只需求A的根节点root(A),B的根节点root(B),令a[ root(A) ] = root(B)就可以,具体代码如下:


for(int i=0; i<n; i++)    //初始化并查集
{
    a[i]=i;    //每个节点都是自己的根节点
}

int fsearch(int x)   //返回并查集中x节点的根节点
{
    int f=a[x];
    while(f!=a[f])    //只有a[f]==f时,f才是根节点
    {
        f=a[f];
    }
    a[x]=f;    //更新x的根节点,让其直接指向f
    return f;
}


void a_add(int x, int y)    //将两个顶点连通
{
    int kx=fsearch(x);    //x的根节点
    int ky=fsearch(y);    //y的根节点
    a[ky]=kx;    //让ky的根节点变成kx
}

 

    原文作者:夏至夏至520
    原文地址: https://blog.csdn.net/qq_41727666/article/details/82952301
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。