HDU 1102 Constructing Roads
2011-07-19 10:43:02

m 条已有道路，让你在这个基础上添加适当的道路，使得所有村庄之间都是联通的，求添加道路的最短距

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 }