MST(最小生成树)——Prim算法——HDU 1879-继续畅通工程

时间：2021-04-01 14:53:23

Prim算法很好理解，特别是学完了迪杰斯特拉算法之后，更加能理解Prim的算法思想

和迪杰斯特拉算法差不多，由于最后要形成连通图，故任意指定一个点，作为初始点，遍历所有点，以当前最小权值的点（和迪杰斯特拉不同，每个点的值就由边的权值确定）每次求出其他点的值。

在判断联通图的关系时，并查集是个十分高效的手段，通过并查集能够判断出当前是否成环（在Kruskal算法里用并查集判断是否成环非常重要），还有判断当前是否有路可通

通过HDU 1879来分析Prim算法，以及并查集在MST中的应用

继续畅通工程

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
 

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。

 

Output

每个测试用例的输出占一行，输出全省畅通需要的最低成本。
 

Sample Input

3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
 

Sample Output

3
1
 
 
#include <iostream>

#include <cstdio>

#include <cstring>

#define  inf 10000000

using namespace std;

int towns[][]; //用邻接矩阵存贮图中边的权值

int lowcost[];   //存贮点的值

bool vis[];

int father[];

int findset(int x) //经典的并查集 路径压缩查找root节点，接下来要用到它

{

    if (x!=father[x])

     father[x]=findset(father[x]);

    return father[x];

}

int main()

{

    int n,m;

    while (scanf("%d",&n)&&n)

    {

        int i,j,k;

        m=n*(n-)/;

        for (i=; i<=n; i++) //初始化部分，我一般首先将边和点的值全部初始化为inf

        {

            for (j=;j<=n;j++)

               towns[i][j]=inf;

            father[i]=i;

            lowcost[i]=inf;

        }

        for (j=;j<=m;j++)  //读入边的权值

        {

            int a,b,c,d;

            scanf("%d %d %d %d",&a,&b,&c,&d);

            if (d==)     //根据题目要求，d为1的时候代表路已经修通，故用并查集把所有修通了路的节点汇集在一个集合中

            {

                int root=findset(a);

                int r2=findset(b);

                father[r2]=root;

            }

            else

            if (towns[a][b]>c) //有些题目会比较坑，两点之间有多条路，而且题目里面还没有任何提示，所以加上这句判断较为保险

             towns[a][b]=towns[b][a]=c; //无向图，双向都要设置权值

        }

        lowcost[]=; //我一般设置从1点出发进行连通，故将点1的权值设置为0

        memset(vis,,sizeof vis);

        int ans=;

        for (i=; i<=n; i++)  //prim核心部分。
 {

            int min=inf,loc=;

            for (j=;j<=n;j++) //先找出lowcost最小的点，即点权值最小的点

            {

                if (vis[j]||lowcost[j]==inf) continue;

                if (min>lowcost[j]) min=lowcost[j],loc=j;

            }

            vis[loc]=; //通过vis数组将已经连通且权值最小的点 设置为已访问状态。

            ans+=lowcost[loc]; //prim里面点的权值和Dijstla不同，这里保存的就是连通边的权值。所以求结果的时候是累加点权值即可

            for (k=;k<=n;k++)

            {

                if (findset(k)==findset(loc)) towns[loc][k]=;//并查集派上用场了，一旦并查为同一集合，说明路已经修好，边权值设置为0

                if (k==loc||vis[k]) continue;

                if (lowcost[k]>towns[loc][k]) //由当前点向其他未连通点 进行 “尝试连通”

                  lowcost[k]=towns[loc][k];

            }

        }

       printf("%d\n",ans);

    }

    return ;

}

相关文章