请通过C++使用prim算法和kruskal算法编程实现最小生成树

以下是C++实现Prim算法和Kruskal算法求最小生成树的示例代码：

Prim算法：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n;
int g[MAXN][MAXN];
int d[MAXN];
bool vis[MAXN];

void prim(int s) {
    memset(d, INF, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(d[s], s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int v = 1; v <= n; v++) {
            if (g[u][v] < INF && !vis[v] && g[u][v] < d[v]) {
                d[v] = g[u][v];
                pq.push(make_pair(d[v], v));
            }
        }
    }
}

int main() {
    int m;
    cin >> n >> m;
    memset(g, INF, sizeof(g));
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    prim(1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (d[i] == INF) {
            cout << "No solution!" << endl;
            return 0;
        }
        ans += d[i];
    }
    cout << ans << endl;
    return 0;
}

Kruskal算法：

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

const int MAXN = 1005;

int n;
int fa[MAXN];

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

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

int kruskal() {
    int ans = 0, cnt = 0;
    sort(edges, edges + n * (n - 1) / 2);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < n * (n - 1) / 2; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
            ans += w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return ans;
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = { u, v, w };
    }
    cout << kruskal() << endl;
    return 0;
}