HDU 1102 Constructing Roads这个题目的意思就是说，给你一个有n个村庄的地图，map[i][j]表示从村庄 i 到村庄 j 的距离，然后给你
m 条已有道路，让你在这个基础上添加适当的道路，使得所有村庄之间都是联通的，求添加道路的最短距
离的值。 典型的最小生成树算法的运用。
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4
5 const int MAX = 0x7fffffff;
6 int map[101][101], v[101], x, y, n, sum, flag, min;
7
8 void Reset(int n)
9 {//根据 规模 n 的大小 ，建立 map！
10 for (int i=0; i<n; i++)
11 {
12 for (int j=0; j<n; j++)
13 {
14 scanf("%d", &map[i][j]);
15 if (i == j)map[i][j] = 0;
16 }
17 }
18 int m;
19 scanf("%d", &m);
20 for (int i=0; i<m; i++)
21 {
22 scanf("%d %d", &x, &y);
23 map[x-1][y-1] = map[y-1][x-1] = 0;
24 }
25 }
26 void MinTree()
27 {// 最小生成树算法
28 memset(v, 0, sizeof(v));
29 v[0] = 1;
30 sum = 0;
31 for (int i=1; i<n; i++)
32 {
33 min = MAX;
34 for (int j=0; j<n; j++)
35 {
36 if (!v[j] && map[0][j] < min)
37 {
38 min = map[0][j], flag = j;
39 }
40 }
41 v[flag] = 1;
42 sum += min;
43 for (int j=0; j<n; j++)
44 {
45 if (!v[j] && map[0][j] > map[flag][j])
46 {
47 map[0][j] = map[flag][j];
48 }
49 }
50 }
51 printf("%d\n", sum);
52 }
53
54 int main()
55 {
56 while (scanf("%d", &n) != EOF)
57 {
58 Reset(n);
59 MinTree();
60 }
61 return 0;
62 }