最小生成樹
題目描述
給定一個 n 個點 m 條邊的無向圖，圖中可能存在重邊和自環，邊權可能為負數。
求最小生成樹的樹邊權重之和。如果最小生成樹不存在，則輸出 impossible。
給定一張邊帶權的無向圖 G = (V, E)，其中：
- V 表示圖中點的集合，n = |V|
- E 表示圖中邊的集合，m = |E|
由 V 中的全部 n 個頂點和 E 中 n - 1 條邊構成的無向連通子圖被稱為 G 的一棵生成樹，其中邊的權值之和最小的生成樹被稱為無向圖 G 的最小生成樹。
輸入格式
- 第一行包含兩個整數
n和m。 - 接下來
m行，每行包含三個整數u,v,w，表示點u和點v之間存在一條權值為w的邊。
輸出格式
- 共一行：
- 若存在最小生成樹，則輸出一個整數，表示最小生成樹的樹邊權重之和。
- 如果最小生成樹不存在，則輸出
-1。
c++代碼
#include<bits/stdc++.h>using namespace std;struct edge{int a, b, val;
};struct mycmp{bool operator()(const edge& a, const edge& b) { return a.val > b.val; }
};int main() {int n, m, a, b, c;edge e;cin >> n >> m;vector<vector<edge>> edges(n + 1);for (int i = 0; i < m; i++) {cin >> a >> b >> c;e.a = a, e.b = b, e.val = c, edges[a].push_back(e);e.b = a, e.a = b, edges[b].push_back(e);}priority_queue<edge, vector<edge>, mycmp> q;vector<bool> vis(n + 1, false);vector<edge> ans;int start = 1;for (int i = 0; i < n - 1; i++) {vis[start] = true;for (edge x : edges[start]) if (!vis[x.b]) q.push(x);while(!q.empty() && vis[q.top().b]) q.pop();if (q.empty()) {cout << -1;return 0;}e = q.top(), ans.push_back(e), q.pop(), start = e.b;}int sum = 0;for (edge x : ans) sum += x.val;cout << sum;return 0;
}
)
