7-4 最小生成树 分数 100 作者 tgiwx 单位 兰州大学 给定结点数为 n，边数为 m 的带权无向连通图 g，所有结点编号为 1,2,⋯,n。 求 g 的最小生成树的边权和。 输入格式: 第一行两个正整数 n,m。 之后的 m 行，每行三个正整数u i ​ ,v i ​ ,w i ​ (1≤u i ​ ,v i ​ ≤n,0≤w i ​ ≤10 9 )，描述一条连接结点 u i ​ 和 v i ​ ，边权为 w i ​ 的边。 输出格式: 一个整数表示 g 的最小生成树的边权和。

以下是使用 Prim 算法解决此问题的 C++代码： ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; const int MAXN = 10005; // 最大节点数 const int INF = 1e9; // 无穷大 int n, m; // 节点数和边数 vector<pair<int, int>> graph[MAXN]; // 邻接表存储图 bool visited[MAXN]; // 标记节点是否已访问 int prim() { int res = 0; // 结果 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 最小堆 pq.push({0, 1}); // 从第一个节点开始 while (!pq.empty()) { auto cur = pq.top(); // 取出当前最小边 pq.pop(); int cost = cur.first; // 边权 int node = cur.second; // 节点 if (visited[node]) continue; // 如果已访问过，跳过 visited[node] = true; // 标记已访问 res += cost; // 累加边权 for (auto edge : graph[node]) { // 遍历相邻节点 if (!visited[edge.first]) { // 如果未访问 pq.push({edge.second, edge.first}); // 加入堆 } } } return res; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } cout << prim() << endl; return 0; } ``` 额外需要注意的逻辑点： 1. 邻接表的构建要确保准确，不要遗漏边。 2. 最小堆的操作要注意优先级的设置。 3. 标记已访问节点时要确保正确，避免重复计算。 [2024-12-15 15:49:02 | AI写代码神器 | 504点数解答]