Comment

Fabulous: 2024-01-10 21:43:01
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

#define INF 100000

typedef pair<int, int> pii;

vector<vector<pii>> adj; // 图的邻接表
vector<bool> visited; // 用于记录顶点是否被访问

// Prim算法实现
int prim(int start) {
    int n = adj.size();
    int mstWeight = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq; // 优先队列用于选择下一个要添加到最小生成树的边

    pq.push(make_pair(0, start)); // 从给定顶点开始，权重为0
    while (!pq.empty()) {
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();
        if (visited[u]) continue; // 跳过已访问的顶点
        visited[u] = true;
        mstWeight += w;
        for (auto &v : adj[u]) {
            if (!visited[v.first]) {
                pq.push(make_pair(v.second, v.first)); // 添加与当前顶点相连的边
            }
        }
    }
    return mstWeight;
}

int main() {
    int T;
    cin >> T; // 输入的组数
    while (T--) {
        int n, m;
        cin >> n >> m; // 顶点个数和边的个数

        adj.resize(n); // 调整邻接表大小
        visited.resize(n, false); // 将所有顶点标记为未访问

        // 读入边的信息，构建邻接表
        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            adj[a - 1].push_back(make_pair(b - 1, c));
            adj[b - 1].push_back(make_pair(a - 1, c));
        }

        int mstWeight = prim(0); // 从顶点0开始寻找最小生成树
        cout << mstWeight << endl; // 输出最小生成树的权重
    }
    return 0;
}