HDU 1102 Constructing Roads這個(gè)題目的意思就是說(shuō)，給你一個(gè)有n個(gè)村莊的地圖，map[i][j]表示從村莊 i 到村莊 j 的距離，然后給你
m 條已有道路，讓你在這個(gè)基礎(chǔ)上添加適當(dāng)?shù)牡缆?，使得所有村莊之間都是聯(lián)通的，求添加道路的最短距
離的值。 典型的最小生成樹(shù)算法的運(yùn)用。
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 {//根據(jù) 規(guī)模 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 {// 最小生成樹(shù)算法
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 }