hihocoder(1109) 堆优化的Prim算法

浏览数：49 / 时间：2015年06月08日

这题思路也很简单，就是用一个最大堆堆去维护Prim算法中的Low数组，把刷新Low数组的操作，变成了刷新堆的操作，由于堆的插入操作位logn,查询时间为常数，因此在边稀疏的情况下，其复杂度与Kruscal接近。这题刚开始老是WA，想了很久，不知道错在哪里，后来发现时因此不能直接去堆中的最小路径，因为这条路径的另一个端点有可能已经被用过了。

后来终于发现了，AC。

另外，这一题其实可以直接用priority_queue，代码会少很多呢。

Impl：

 1 int N, E;
 2 vector<pair<int, int> > vertices[100010];
 3 vector<pair<int, int> > edges;
 4 bool used[100010];
 5 
 6 bool cmp(pair<int, int> &p1, pair<int, int> &p2) {
 7     return p1.second > p2.second;
 8 }
 9 
10 unsigned long long prim()
11 {
12     unsigned long long res = 0;
13     int n = N - 1;
14     used[1] = true;
15     for (size_t j = 0; j < vertices[1].size(); ++j)
16         edges.push_back(vertices[1][j]);
17     make_heap(edges.begin(), edges.end(), cmp);
18 
19     while (n--) {
20         while (used[edges[0].first]) {//剔除已经用过的顶点，不要忘记
21             pop_heap(edges.begin(), edges.end(), cmp);
22             edges.pop_back();
23         }
24         pair<int, int> minEdge = edges[0];
25         res += minEdge.second;
26         used[minEdge.first] = true;
27         pop_heap(edges.begin(), edges.end(), cmp);
28         edges.pop_back();
29 
30         for (size_t i = 0; i < vertices[minEdge.first].size(); ++i) {
31             if (!used[vertices[minEdge.first][i].first]) {
32                 edges.push_back(vertices[minEdge.first][i]);
33                 push_heap(edges.begin(), edges.end(), cmp);
34             }
35         }
36     }
37 
38     return res;
39 }
40 
41 int main()
42 {
43     int u, v, w;
44     scanf("%d%d", &N, &E);
45     for (int i = 0; i < E; ++i)
46     {
47         scanf("%d%d%d", &u, &v, &w);
48         vertices[u].push_back(make_pair(v, w));
49         vertices[v].push_back(make_pair(u, w));
50     }
51 
52     printf("%d\n", prim());
53     return 0;
54 }