最小生成树剪枝的c++代码

以下是最小生成树剪枝的C++代码，使用Prim算法实现：

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

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

struct Edge {
    int v, w;
    Edge(int v, int w): v(v), w(w) {}
};

bool operator < (const Edge& a, const Edge& b) {
    return a.w > b.w; // 重载运算符，按权值从小到大排序
}

vector<Edge> G[MAXN];
int dis[MAXN];
bool vis[MAXN];

int prim(int n, int s) {
    int res = 0;
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    priority_queue<Edge> q;
    dis[s] = 0;
    q.push(Edge(s, 0));
    while (!q.empty()) {
        int u = q.top().v; q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        res += dis[u];
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v, w = G[u][i].w;
            if (!vis[v] && w < dis[v]) {
                dis[v] = w;
                q.push(Edge(v, w));
            }
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }
    int ans = INF;
    for (int i = 0; i < n; i++) { // 枚举起点
        for (int j = 0; j < G[i].size(); j++) { // 枚举该点的所有边
            int v = G[i][j].v, w = G[i][j].w;
            G[i][j].w = INF; // 将这条边断开
            ans = min(ans, prim(n, i)); // 计算剩余部分的最小生成树
            G[i][j].w = w; // 恢复这条边
        }
    }
    cout << ans << endl;
    return 0;
}

注：这里使用了邻接表存储图，复杂度为O(mlogn)