Prim!
一個農夫市長想要在鄉鎮內所有農場建構網路，他必須連結所有農場，在農場間拉光纖必須花費成本。給定每對農場間拉光纖需要的成本，現在要以最小成本連接所有農場，任兩農場間都必須可以通訊（可以藉由中介通訊），求最小成本是多少？
第一行 1 個正整數 ，代表有 個農場。 接下來是一個 的矩陣，代表農場間要拉光纖的花費。
一個整數，代表最小成本。
直接套用 Prim 演算法，求出最小生成樹的成本是多少。 這題使用複雜度 的 Prim 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
#include <queue>
#include <functional>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int scale=105;
const int INF=1e9+7;
int gra[scale][scale];
int N;
bool used[scale];
int d[scale];
int prim() {
typedef pair<int, int> IPI; //weight, node
fill(used, used+N, false);
fill(d, d+N, INF);
int total=0;
d[0]=0;
for(;;) {
int v=-1;
for(int u=0; u<N; ++u) {
if(!used[u] && (v==-1 || d[u]<d[v])) v=u;
}
if(v==-1)break; // All good
used[v]=true;
total+=d[v];
for(int u=0; u<N; ++u) {
d[u] = min(d[u], gra[v][u]);
}
}
return total;
}
int main(void) {
while( scanf("%d",&N)==1) {
for(int i=0; i<N; ++i) for(int j=0; j<N; ++j)
scanf("%d",&gra[i][j]);
printf("%d\n", prim());
}
return 0;
}