最小生成树:将所有节点连接起来用到的最小的权重。(图必须是联通图)
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")