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
通过分析，我使用了构建最小生成树的Prim算法，代码如下
#include <bits/stdc++.h> #define N 105 using namespace std; typedef struct { int vexs[N]; int arcs[N][N]; int vexnum, arcnum; } Graph;//图的结构体 int D[N] = {0} ; int visited[N] = {0} ; void Create_G(Graph &G)//创建图，输入结点和个节点的距离 { cin >> G.vexnum ; int i,j; int m=G.vexnum; for(i = 1; i <= m; ++i) { for(j = 1; j <=m ; ++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;//已建成的置距离为0 visited[a]=1; visited[b]=1;//标记为已访问 } } int Prim_Road(Graph G)//prim算法实现 { int i,j,k=1,mi; int cost = 0; int nums = G.vexnum; for(i = 1 ; i <= nums; ++i) { D[i] = G.arcs[1][i]; visited[i] = 0 ; } D[1] = 0 ; visited[1] = 1 ;//初始化数组D[]存储权值，数组visited[]标记已被访问 for(i = 1; i <= nums; ++i) { mi=INT_MAX; for(j=1;j<=nums;++j)//寻找权值最小的边，且未被访问，记录其下标为k { if(D[j]<mi&&!visited[j]) { mi=D[j]; k=j; } } cost += D[k]; //计算所需距离 D[k]=0;//将k点到原点的距离置为0 visited[k] = 1;//将k点标记为已被访问 for(j = 1 ; j <= nums; ++j) { if(G.arcs[k][j] < D[j] && !visited[j]) { D[j] = G.arcs[k][j];//更新数组D[] } } } return cost; } int main() { Graph G; Create_G(G); cout << Prim_Road(G) << endl; return 0; }