[MST_prim] PKU 1258 AgriNet

prim入门练习题。

prim的流程如下：

// 清空顶点集；

任选一个点u作为起点，加入顶点集，从u出发选一条最小边(u, v)，将v加入顶点集，重复直到所有点都进入顶点集。

其中最小边可以用堆来做，还可以用邻接表加速（这里嫌麻烦）。

 1 # include <cstdio>
 2 # include <queue>
 3 
 4 using namespace std;
 5 
 6 typedef pair<int, int> pii;
 7 
 8 # define N (100 + 5)
 9 # define INF 0x7FFFFFFF
10 
11 int n;
12 int g[N][N];
13 
14 int prim(void)
15 {
16     priority_queue <pii, vector<pii>, greater<pii> > Q;
17     int key[N];
18     char vis[N];
19     for (int i = 1; i <= n; ++i)
20     {
21         vis[i] = 0;
22         key[i] = (i==1 ? 0:INF);
23     }
24     Q.push(make_pair(key[1], 1));
25     int ans = 0;
26     while (!Q.empty())
27     {
28         int u = Q.top().second; Q.pop();
29         if (!vis[u]) ans += key[u];
30         vis[u] = 1;
31         for (int i = 1; i <= n; ++i) if (!vis[i] && g[u][i] < key[i])
32         {
33             key[i] = g[u][i];
34             Q.push(make_pair(key[i], i));
35         }
36     }
37     return ans;
38 }
39 
40 void read_graph(void)
41 {
42     for (int i = 1; i <= n; ++i)
43     for (int j = 1; j <= n; ++j)
44         g[i][j] = INF;
45     
46     for (int i = 1; i <= n; ++i)
47     for (int j = 1; j <= n; ++j)
48     {
49         int x;
50         scanf("%d", &x);
51         if (g[i][j] > x) g[j][i] = g[i][j] = x;
52     }
53 }
54 
55 int main()
56 {
57     while (~scanf("%d", &n))
58     {
59         read_graph();
60         printf("%d\n", prim());
61     }
62     
63     return 0;
64 }

kruskal相对较简洁，适用于稀疏图。