HDU 1233 還是暢通工程
題目意思就是給你一個(gè)有n個(gè)點(diǎn)的圖，給出n *（n-1）/ 2 條邊的信息，包括邊的端點(diǎn)和邊的長度，要求
在滿足所有點(diǎn)在同一個(gè)連通分支上的前提下，選擇最短的道路來修建。典型的最小生成樹算法，同樣，問題
規(guī)模不大，直接矩陣就可以勝任。
1 #include<stdlib.h>
2 #include<stdio.h>
3 #include<string.h>
4
5 const int MAX = 100000000;
6 int map[101][101], MIN, sum;
7 // map[i][j] 記錄從點(diǎn) i 到點(diǎn) j 的距離 ！
8
9 int main()
10 {
11 int n, x, y, m, v[101], flag, dis;
12 while (scanf("%d", &n), n)
13 {
14 map[n][n];
15 memset(map, 0, sizeof(map));//數(shù)組清零
16 m = (n*(n-1))/2;
17 for (int i=0; i<m; i++)
18 { //輸入并處理邊的信息
19 scanf("%d %d %d", &x, &y, &dis);
20 map[x-1][y-1] = map[y-1][x-1] = dis;
21 }
22 for (int i=0; i<n; i++)map[i][i] = MAX;
23 //建圖完成 ！
24 v[n];
25 memset(v, 0, sizeof(v));
26 v[0] = 1;
27 sum = 0;
28 for (int i=1; i<n; i++)
29 {//prim 算法求最小生成樹
30 MIN = 10000000;
31 for (int j=0; j<n; j++)
32 {
33 if (!v[j] && map[0][j] < MIN)
34 {
35 MIN = map[0][j];
36 flag = j;
37 }
38 }
39 sum += MIN;
40 v[flag] = 1;
41 for (int j=0; j<n; j++)
42 {
43 if (!v[j] && map[0][j] > map[flag][j])
44 {
45 map[0][j] = map[flag][j];
46 }
47 }
48 }
49 printf("%d\n",sum);
50 }
51 return 0;
52 }
53