60 lines
1.5 KiB
C++
60 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int INF = 1e9;
|
||
|
||
// Prim 最小生成树（堆优化）
|
||
// 输入：无向图（n 点，m 边），从任意点开始生成 MST
|
||
// 输出：MST 总权值；若图不连通，返回 -1
|
||
|
||
struct Edge {
|
||
int to, w;
|
||
};
|
||
|
||
int prim(int n, vector<vector<Edge>>& g) {
|
||
vector<int> dist(n, INF); // dist[v] = 当前未加入 MST 的点 v 到 MST 的最小边权
|
||
vector<bool> in(n, false); // in[v] = 点 v 是否已加入 MST
|
||
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
|
||
|
||
dist[0] = 0; // 任意选择 0 号点作为起点
|
||
pq.push({0, 0});
|
||
|
||
int mst_cost = 0;
|
||
int count = 0;
|
||
|
||
while (!pq.empty()) {
|
||
auto [d, v] = pq.top();
|
||
pq.pop();
|
||
|
||
if (in[v]) continue; // 已入 MST 的点无需再处理
|
||
in[v] = true;
|
||
mst_cost += d;
|
||
count++;
|
||
|
||
for (auto &e : g[v]) {
|
||
int u = e.to, w = e.w;
|
||
if (!in[u] && w < dist[u]) { // 若 u 未加入 MST 且发现更小边
|
||
dist[u] = w;
|
||
pq.push({w, u}); // 推入堆中
|
||
}
|
||
}
|
||
}
|
||
|
||
if (count < n) return -1; // 图不连通
|
||
return mst_cost;
|
||
}
|
||
|
||
int main() {
|
||
int n, m;
|
||
cin >> n >> m;
|
||
vector<vector<Edge>> g(n);
|
||
|
||
for (int i = 0; i < m; i++) {
|
||
int u, v, w;
|
||
cin >> u >> v >> w;
|
||
g[u].push_back({v, w});
|
||
g[v].push_back({u, w});
|
||
}
|
||
|
||
cout << prim(n, g) << endl;
|
||
}
|