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

最小生成树问题是指在一个加权无向连通图中，找到一棵边权值之和最小的生成树。贪心算法是求解该问题的一种常用方法。

具体思路如下：

1. 选择一个起点，将其作为生成树的根节点。

2. 按照边权值从小到大的顺序，依次将边加入生成树中。如果加入该边后会形成环，则不加入，直接考虑下一条边。

3. 重复步骤2，直到生成树包含所有顶点。

C++代码实现如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 1005;
const int inf = 1e9; // 无穷大

int n, m; // n表示顶点数，m表示边数
vector<pair<int, int>> g[maxn]; // 存储图的邻接表
bool vis[maxn]; // 标记每个顶点是否已加入生成树

int prim() { // 返回最小生成树的边权和
    int res = 0; // 最小生成树的边权和
    vis[1] = true; // 将1号顶点加入生成树
    for (int i = 1; i < n; i++) { // 遍历n-1次，每次加入一个顶点
        int u = -1, d = inf; // u表示待加入生成树的顶点，d表示u与生成树中的某个顶点之间的最短边权
        for (int j = 1; j <= n; j++) { // 找到距离生成树最近的顶点u
            if (vis[j]) {
                for (auto& e : g[j]) {
                    int v = e.first, w = e.second;
                    if (!vis[v] && w < d) {
                        d = w;
                        u = v;
                    }
                }
            }
        }
        if (u == -1) return -1; // 无法构成生成树，返回-1
        vis[u] = true; // 将u加入生成树
        res += d; // 将u与生成树中的某个顶点之间的最短边权加入最小生成树的边权和
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) { // 读入图的边
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int ans = prim(); // 求解最小生成树
    if (ans == -1) cout << "无法构成生成树" << endl;
    else cout << ans << endl;
    return 0;
}

该代码中，使用邻接表存储图，vis数组表示每个顶点是否已加入生成树。prim函数返回最小生成树的边权和，如果无法构成生成树，则返回-1。