PTA 修建道路 (30分)

修建道路 (30分)

代码长度限制 16 KB
时间限制 1000 ms
内存限制 64 MB

题目描述：

N个村庄，从1到N编号，现在请您兴建一些路使得任何两个村庄彼此连通。我们称村庄A和B是连通的，当且仅当在A和B之间存在一条路，或者存在一个存在C，使得A和C之间有一条路，并且C和B是连通的。
已知在一些村庄之间已经有了一些路，您的工作是再兴建一些路，使得所有的村庄都是连通的，并且兴建的路的长度是最小的。

输入格式:

第一行是一个整数N（3<=N<=100），代表村庄的数目。后面的N行，第i行包含N个整数，这N个整数中的第j个整数是第i个村庄和第j个村庄之间的距离，距离值在[1,1000]之间。
然后是一个整数Q(0<=Q<=N*(N+1)/2)。后面给出Q行，每行包含两个整数a和b（1<=a<b<=N），表示在村庄a和b之间已经兴建了路。

输出格式:

输出一行仅有一个整数，表示为使所有的村庄连通需要新建公路的长度的最小值。

输入样例:

3
0 990 692
990 0 179
692 179 0
1
1 2

输出样例:

179

解题思路:

无向图最短路径问题，要求没有连接的路的最短长度，先求出联通图最短路径的长度，再减去已经存在的路径的长度。所以将原来已经存在的路的权值设为 0，因为已经连好的路是0，所以一定会经过已经连好的路，此时只记录整个图的最短路径就是所需要铺设的路的长度。

答案：

#include <bits/stdc++.h>
#define MAX_VEX_NUM 105
using namespace std;typedef struct
{int vexs[MAX_VEX_NUM];int arcs[MAX_VEX_NUM][MAX_VEX_NUM];int vexnum, arcnum;
} Graph;int lowcost[MAX_VEX_NUM] = {0} ; //记录最短路径
int visited[MAX_VEX_NUM] = {0} ; //记录是否访问过void Create_G(Graph &G)
{cin >> G.vexnum ;int i,j,preroad = 0;for(i = 1; i <= G.vexnum; ++i)for(j = 1; j <= G.vexnum ; ++j)G.arcs[i][j] = INT_MAX;for(i = 1; i <= G.vexnum; ++i){for(j = 1; j <= G.vexnum ; ++j){cin >> G.arcs[i][j];}}int n;cin >> n ;for( i = 0 ; i < n ; ++i){int a,b;cin >> a >> b ;G.arcs[a][b] = G.arcs[b][a] = 0; //有路的边全部清零visited[a];visited[b];}
}int minadj(int a[],int n)
{int lowest = INT_MAX;int k = 1;for( int i = 1; i <= n; i++ ){if( a[i] < lowest && !visited[i] ){lowest = a[i];k = i;}}return k;
}int Prim_Road(Graph G)
{int i,j,k;int cost = 0;   //记录需要铺设的最短的路int nums = G.vexnum;for(i = 1 ; i <= nums; ++i){lowcost[i] = G.arcs[1][i];visited[i] = 0 ;}//从第一个顶点开始lowcost[1] = 0 ;visited[1] = true ;for(i = 1; i <= nums; ++i){k = minadj(lowcost,nums);  //找到最小边的邻接点cost += lowcost[k];  //因为已经连好的路是0，所以一定会经过已经连好的路，此时只记录整个图的最短路径就是所需要铺设的路的长度visited[k] = true;// lowcost[k] = 0;for(j = 1 ; j <= nums; ++j){if(G.arcs[k][j] < lowcost[j] && !visited[j]){lowcost[j] = G.arcs[k][j];}}}return cost;
}int main()
{Graph G;Create_G(G);cout <<   Prim_Road(G) << endl;return 0;
}

运行结果：