C++使用贪心算法解决最小生成树问题

最小生成树问题有多种解决方法，其中一种是使用贪心算法。在C++中，使用贪心算法解决最小生成树问题的步骤如下：

1. 确定图的边集合，并根据边权值从小到大排序。

2. 初始化一个空的边集合，这个边集合最终就是最小生成树。

3. 从排序后的边集合中依次选取边加入到边集合中，如果这条边所连接的两个点不在同一个连通块中，则将这条边加入到边集合中，同时将这两个点合并到同一个连通块中。

4. 重复步骤3，直到所有的点都在同一个连通块中为止。

下面是使用 Kruskal 算法实现的代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &e) const { return w < e.w; }
};

int fa[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; ++i) fa[i] = i;
    vector<Edge> ans;
    for (Edge e : edges) {
        if (find(e.u) != find(e.v)) {
            merge(e.u, e.v);
            ans.push_back(e);
        }
    }
    int sum = 0;
    for (Edge e : ans) sum += e.w;
    cout << sum << endl;
    return 0;
}

其中，`Edge` 表示一条边的结构体，`vector<Edge> edges` 存储所有的边，`vector<Edge> ans` 存储最小生成树中的边，`fa` 数组表示并查集的父亲数组。在代码中，我们首先将所有的边按照权值排序，然后使用并查集维护连通性，并将边加入到最小生成树中，最后计算最小生成树的权值和输出即可。