Comment

Huhu_Miao: 2024-11-16 22:07:11

/**
 *    minimum_spanning_tree_n^2
 *    author:  Huhu_Miao
 *    created: 2024.11.13 18:00:00 (UTC+8)
**/
#include<bits/stdc++.h>
using pii = std::pair<int,int>;

void solve(){
	int ans = 0;
	int n , m;
	std::cin >> n >> m;
	std::deque<bool> vis(n+1,false);
	std::vector<std::vector<pii>> graph(n+1,std::vector<pii>(0));
	for(int i = 0 ; i < m ; i++){
		int a , b , w;
		std::cin >> a >> b >> w;
		graph[a].emplace_back(b,w);
		graph[b].emplace_back(a,w);
	}
	vis[1] = true;
	for(int i = 0 ; i < n-1 ; i++){
		int minWeight = std::numeric_limits<int>::max();
		int minPoint = -1;
		for(int i = 1 ; i < n+1 ; i++){
			if(!vis[i]) continue;
			for(auto elem: graph[i]){
				if(vis[elem.first]) continue;
				minWeight = std::min(minWeight,elem.second);
				if(minWeight == elem.second) minPoint = elem.first;
			}
		}
		ans += minWeight;
		//if(minPoint == -1) throw std::logic_error("unexcepted exception.");
		vis[minPoint] = true;
	}

	std::cout << ans << '\n';
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin>>T;

	while(T--){
		solve();
	}

	return 0;
}

Huhu_Miao: 2024-11-16 22:05:53

/**
 *    minimum_spanning_tree
 *    author:  Huhu_Miao
 *    created: 2024.11.13 19:41:00 (UTC+8)
**/
#include<bits/stdc++.h>
using pii = std::pair<int,int>;

void solve(){
	int ans = 0;
	int n , m;
	std::cin >> n >> m;
	
	std::deque<bool> vis(n+1,false);
	std::vector<std::vector<pii>> graph(n+1,std::vector<pii>(0));
	std::vector<int> minEdgeWeight(n+1,std::numeric_limits<int>::max());
	std::priority_queue<pii,std::vector<pii>,std::greater<pii>> minHeap;

	while(m--){
		int a, b, w;
		std::cin >> a >> b >> w;
		graph[a].emplace_back(b,w);
		graph[b].emplace_back(a,w);
	}

	minHeap.emplace(0,1);
	while(!minHeap.empty()){
		auto [w,u] = minHeap.top();
		minHeap.pop();
		if(vis[u]) continue;
		vis[u] = true;
		ans += w;
		for(const auto & [v,w] : graph[u]){
			if(!vis[v] && w < minEdgeWeight[v]){
				minEdgeWeight[v] = w;
				minHeap.emplace(w,v);
			}
		}
	}

	std::cout << ans << '\n';
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin>>T;

	while(T--){
		solve();
	}

	return 0;
}

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;
}