【数据结构】PTA 公路村村通（最小生成树Prim算法引入）

在<span style='color:#A52A2A'>[**PTA**](https://pintia.cn/)</span>发现一道题，<span style='color:#A52A2A'>[**公路村村通**](https://pintia.cn/problem-sets/15/problems/718)</span>

![](https://blog.fivk.cn/usr/uploads/2021/08/1071147818.png)

感觉这个题拿来做Prim算法引入很不错。

7-10 公路村村通 (30 分)

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

### 输入格式:

输入数据包括城镇数目正整数**N**（**≤** **1000**）和候选道路数目**M**（**≤** **3** **N**）；随后的**M**行对应**M**条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到**N**编号。

### 输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出 **−** **1**，表示需要建设更多公路。

### 输入样例:

```in
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
```

### 输出样例:

```out
12
```

---

**解题思路：**

1.这道题一开始走偏了想直接同floyd算法求出最短路径然后相加了

**最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。
最短路径是从一点出发，到达目的地的路径最小。**

</div>

2.理清楚了最小生成树与最短路径之间的区别以后就很容易想到用最小生成树算法了，这里选用的是Prim算法

```cpp
#include<stdio.h>
#include<stdlib.h>

#define MAXVEX 1003
#define INFINITY  65535

void CreateGraph( );
int  Prim();

int G[MAXVEX][MAXVEX],Nv,Ne;

int main()
{
    int f = 0;

scanf("%d %d",&Nv,&Ne);
    CreateGraph();
    f =Prim();
    printf("%d",f);

return 0;
}

void CreateGraph()
{
    //用邻接矩阵表示图
    int i,j;
    int v1,v2,w;

for( i=1; i<=Nv; i++)
    {
        for( j=1; j<=Nv; j++)
        {
            G[i][j] = INFINITY;  //初始化
        }
    }

for( i=0; i<Ne; i++)  //注意这里是读入边
    {
        scanf("%d %d %d",&v1,&v2,&w);
        G[v1][v2] = w;         //读入权值
        G[v2][v1]= G[v1][v2];  //无向图对称
    }
}

int  Prim()
{
    int min;
    int i,j,k;
    int lowcost[MAXVEX];
    int cost =0;

lowcost[1] = 0;   //初始化第一个权值为0,即v0加入生成树

for( i=2; i<=Nv; i++)
    {
        lowcost[i] = G[1][i];
    }

for( i=2; i<=Nv; i++)
    {
        min = INFINITY;
        j = 1;
        k = 0;
        while( j<=Nv )
        {
            if( lowcost[j]!=0 && lowcost[j]<min)
            {
                min = lowcost[j];
                k = j;   //将当前最小值的下标存入k
            }
            j++;
        }

if(k==0)
        {
            return -1;  //不连通
        }
        cost += min;
        lowcost[k] = 0;   //将当前顶点设置为0，表示此结点已经完成任务

for( j=2; j<=Nv; j++)
        {
            if( lowcost[j]!=0 && G[k][j]<lowcost[j])
            {
                //若下标为k顶点各边权值小于此前这些顶点未被加入生成树的权值
                lowcost[j] = G[k][j];
            }
        }

}

return cost;
}
```

版权©：部分内容来自<span style='color:#A52A2A'></span>[**yuxiaoba**](https://home.cnblogs.com/u/yuxiaoba/)<span style='color:#A52A2A'></span>

最后修改：2021 年 12 月 15 日