题解 | 【模板】最小生成树

最小生成树：将所有节点连接起来用到的最小的权重。（图必须是联通图）

Prim算法：

考虑任意一个点，和这个点连接的所有边中，最短的那一条一定在最小生成树的结果（因为假如别的边都已经连接好了，只差这一个节点，那么连接这个节点最好的办法就是连接他最短的那一条边。这对于任意一个节点都适合）。

在将一个节点和距离其最短的那个节点连接后，这两个节点就形成一个大节点。和这个大节点相连的所有节点中，路径最短的那个节点一定在最终的结果中。这是重复上面的逻辑得到的合理推论。

上述循环，将所有节点连接成大节点，就是最终的结果。

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

int main() {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    int n, m;
    cin >> n >> m;
    vector<vector<tuple<int, int, int>>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w, i + 1);
        graph[v].emplace_back(u, w, i + 1);
    }
    for (auto [v, w, i] : graph[1]) {
        pq.push({w, v, i});
    }
    vector<int> vis(n + 1, 0);
    vis[1] = 1;
    long long ans = 0;
    vector<int> path;
    while (!pq.empty()) {
        auto[w, v, i] = pq.top();
        pq.pop();
        if (vis[v]) continue;
        vis[v] = 1;
        path.push_back(i);
        ans += w;
        for (auto[v, w, i] : graph[v]) {
            pq.push({w, v, i});
        }
    }
    cout << ans << '\n';
    for (int i = 0; i < path.size(); i++) {
        cout << path[i] << ' ';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")