2023Tsinghua-HKUST F <最小生成树 Prim>

// 最小生成树 Prim
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 1e5 + 10;

struct Edge
{
    int v;
    LL w;
};

vector<Edge> adj[N];  // adj[u] 表示从节点 u 出发的 邻接边u->v 的列表, 边指向v, 边权为w 
LL dis[N];  // 用于prim最小生成树
bool vis[N];  // 标记最小生成树过程中节点i是否已经纳入生成树

void solv()
{
    int n, m;
    cin >> n >> m;
    int u, v, w;
    for (int i = 1; i <= m; i ++)
    {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    // Prim
    priority_queue<PII, vector<PII>, greater<PII>> q;  // 堆优化 Prim, 元素为 {d, u}, d为节点u距离当前生成树已有点集合(vis表示为true的节点)的最小距离
    memset(dis, 0x3f, sizeof dis); dis[1] = 0;
    q.push({0, 1});
    vector<int> ans;
    LL tot = 0;  // 最小生成树边权和
    while (q.size())
    {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;
        // 将节点u放入生成树节点集合
        vis[u] = true; 
        ans.push_back(u);  // 记录节点拓展顺序
        tot += dis[u];

        for (auto [v, w]: adj[u])  // cpp语法, 遍历adj[u]中的所有元素, 每个pair的值为{v, w}
        {
            if (w < dis[v])  // 注意prim与dijkstra的堆优化写法很像, 这句是最大的差别; 更新距离是节点v到生成树节点集合, 而不是起点
            {
                dis[v] = w;
                q.push({dis[v], v});
            }
        }
    }

    cout << tot << ' ' << n << endl;
    for (auto u: ans) cout << u << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}