最小优先队列+prim

ゞ浴缸里的玫瑰 2022-02-26 03:44 231阅读 0赞

#include <iostream>
    #include <cstdlib>
    #include <queue>
     
    using namespace std;
    
    class Edge {
      public:
        int beg;
        int end;
        int val;
    
      friend bool operator<(const Edge &, const Edge &);
    };
    
    bool operator<(const Edge &e1, const Edge &e2) {
      return e1.val > e2.val;    // 最小优先队列
    }
    
    const int MAX_N = 100;       // 顶点的最大数量
    bool visit[MAX_N];
    int value[MAX_N][MAX_N];
    int link[MAX_N][MAX_N]; 
    
    int main() {
      int n, m;
      int p, q, v;
      int totVisit, curVertex;
      int ans;
      Edge tmp;
      priority_queue<Edge> edgePQ;
    
      cin >> n >> m;  // n个顶点(标号0 -- n-1，m条边)
    
      for (int i = 0; i != n; ++i) {
        visit[i] = false;
        link[i][0] = 1;
      }
      for (int i = 0; i != m; ++i) {
        cin >> p >> q >> v;
    
        value[p][q] = value[q][p] = v;
        link[p][link[p][0]++] = q;
        link[q][link[q][0]++] = p;
      }
    
      visit[0] = true;
      totVisit = 1;
      curVertex = 0;
      ans = 0;
      while (totVisit++ < n) {
        for (int i = 1; i != link[curVertex][0]; ++i) {
          if (!visit[link[curVertex][i]]) {
            tmp.beg = curVertex;
            tmp.end = link[curVertex][i];
            tmp.val = value[tmp.beg][tmp.end];
    
            edgePQ.push(tmp);
          }
        }
    
        while (!edgePQ.empty() && visit[edgePQ.top().end]) {
          edgePQ.pop();
        }
        tmp = edgePQ.top();
        visit[tmp.end] = true;
        ans += tmp.val;
        curVertex = tmp.end;
    
        edgePQ.pop();
      }
    
      cout << ans << endl;
    
      return EXIT_SUCCESS;
    }

需要注意的地方就是，由于用的是STL中的priority\_queue，所以要重载<操作符。并且其默认的是最大优先队列，所以

重载<操作符的时候要返回的是>的值（ >= 会出错，原因我暂时不是很清楚）。

算法时间复杂度近似于O(ElgV)，基本达到要求。用最小优先队列要比不用而直接每次全部点遍历地找最小的边效率高出

很多（算法导论那本书上说用斐波拉契堆实现的话运行时间可以减少到O(E + VlgV))。