【luogu題解】P1546 最短網路 Agri-Net

• 題目

　　約翰已經給他的農場安排了一條高速的網路線路，他想把這條線路共用給其他農場。為了用最小的消費，他想鋪設最短的光纖去連接所有的農場。

你將得到一份各農場之間連接費用的列表，你必須找出能連接所有農場並所用光纖最短的方案。每兩個農場間的距離不會超過100000。

• 輸入

　　第一行： 農場的個數，N（3<=N<=100）。

　　第二行..結尾: 後來的行包含了一個N*N的矩陣,表示每個農場之間的距離。理論上，他們是N行，每行由N個用空格分隔的數組成，實際上，他們限制在80個字元，因此，某些行會緊接著另一些行。當然，對角線將會是0，因為不會有線路從第i個農場到它本身。

• 輸出

　　只有一個輸出，其中包含連接到每個農場的光纖的最小長度。

• 思路

　　我是用並查集加上貪心過的這道題（ 本來題目就不是很難 ），其中值得註意的地方是由於輸入的矩陣是關於對角線對稱的，所以只用讀入一半就好了。

實現代碼

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 200002;
 7 
 8 struct node {
 9     int st, ed, v;
10 };
11 node a[maxn];
12 
13 int f[maxn];
14 
15 bool cmp ( node a, node b) {
16     return a.v < b.v;
17 }
18 
19 int find ( int k ) {
20     if ( k == f[k] )    return k;
21     else {
22         f[k] = find( f[k] );
23         return f[k];
24     }
25 }
26 
27 int main () {
28     int n, index = 0;
29     scanf ( "%d", &n );
30     for ( int i = 1; i <= n; i ++ ) {
31         for ( int j = 1; j <= n; j ++ ) {
32             int k;
33             scanf ( "%d", &k );
34             if ( j > i ) {
35                 index ++;
36                 a[index].st = i; a[index].ed = j; a[index].v = k; 
37             }   
38         }
39     }
40     for ( int i = 1; i <= n; i ++ )    f[i] = i;
41     sort ( a + 1, a + index + 1, cmp );
42     int ans = 0, p = 1;
43     for ( int i = 1; i <= index; i ++ ) {
44         if ( find( a[i].st ) != find( a[i].ed ) ) {
45             ans += a[i].v;
46             f[find( a[i].st )] = a[i].ed;
47             p ++;
48             if ( p == n )    break; 
49         }
50     }
51     printf ( "%d", &ans );
52     return 0;
53 }