最小生成树Prim方法.cpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 优化 3：加快输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    
    // graph 存 {邻居节点, 权重}
    vector<vector<pair<int,int>>> graph(n + 1);
    
    // 优先队列存 {权重, 目标节点}，利用 greater 按权重从小到大排
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> lwh;
    
    for(int i = 0; i < m; i++)
    {
        int k1, k2, val;
        cin >> k1 >> k2 >> val;
        graph[k1].push_back({k2, val});
        graph[k2].push_back({k1, val});
    }
    
    // 记录节点是否已经在最小生成树中
    vector<bool> s(n + 1, false);
    s[1] = true; 
    
    for(auto& temp : graph[1])
    {
        // 优化 1：颠倒顺序，将 {权重, 节点} 入队
        lwh.push({temp.second, temp.first});
    }
    
    int cnt = 1, ans = 0;
    while(!lwh.empty())
    {
        // 取出当前权重最小的边
        pair<int,int> current_edge = lwh.top();
        lwh.pop();
        
        int weight = current_edge.first;
        int node = current_edge.second;
        
        // 如果该节点还不在树中
        if(!s[node])
        {
            ans += weight;
            cnt++;
            s[node] = true;
            
            // 遍历刚加入树的节点的所有边
            for(auto& temp : graph[node])
            {
                int next_node = temp.first;
                int next_weight = temp.second;
                
                // 优化 2：只有当目标节点不在树中时，才将边入队，减少队列冗余
                if(!s[next_node])
                {
                    lwh.push({next_weight, next_node});
                }
            }
        }
    }
    
    // 优化 3：使用 \n 代替 endl
    if(cnt != n)
        cout << "orz\n";
    else
        cout << ans << "\n";
        
    return 0;
}