经典算法 最小生成树(prim算法)

最小生成树

题目描述

给定一个 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;
}