第八章 电子商务网站建设试题2021年网络营销考试题及答案

### 思路
使用Kruskal算法求解图的最小生成树。Kruskal算法通过对所有边按权值排序，然后逐步选择最小权值的边，确保不会形成环，直到构建出最小生成树。

### 伪代码
1. 读取输入的结点数`n`和边数`m`。
2. 读取每条边的信息，存储在边列表中。
3. 对边列表按权值进行排序。
4. 初始化并查集。
5. 遍历排序后的边列表，逐步选择边并加入最小生成树，确保不会形成环。
6. 输出最小生成树的边权和。

### C++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct Edge {int u, v;long long w;bool operator<(const Edge& other) const {return w < other.w;}
};vector<int> parent, rankVec;int find(int u) {if (parent[u] != u) {parent[u] = find(parent[u]);}return parent[u];
}void unionSets(int u, int v) {int rootU = find(u);int rootV = find(v);if (rootU != rootV) {if (rankVec[rootU] > rankVec[rootV]) {parent[rootV] = rootU;} else if (rankVec[rootU] < rankVec[rootV]) {parent[rootU] = rootV;} else {parent[rootV] = rootU;rankVec[rootU]++;}}
}int main() {int n, m;cin >> n >> m;vector<Edge> edges(m);for (int i = 0; i < m; ++i) {cin >> edges[i].u >> edges[i].v >> edges[i].w;}sort(edges.begin(), edges.end());parent.resize(n + 1);rankVec.resize(n + 1, 0);for (int i = 1; i <= n; ++i) {parent[i] = i;}long long mstWeight = 0;for (const auto& edge : edges) {if (find(edge.u) != find(edge.v)) {unionSets(edge.u, edge.v);mstWeight += edge.w;}}cout << mstWeight << endl;return 0;
}

### 总结
该代码使用Kruskal算法求解图的最小生成树。通过对边按权值排序，使用并查集管理连通性，逐步选择最小权值的边，确保不会形成环，最终输出最小生成树的边权和。