/**
 * @file Prim.cpp
 * @brief 求出最小生成树
 * @details 给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
 * @mainpage main函数读入点数和边数，然后读入每条边的信息，最后调用Prim函数使用Prim算法计算输出最小生成树的权值和，如果Prim返回-1（即图不连通），输出orz。
 * @author Gcc_Gdb_7_8_1
 * @version 1.0
 * @date 2024-8-22
 */

#include <cstdio>
#include <queue>
#include <cstring>

/// @brief 定义边结构体 （1 <= weight <= 10000）
struct Edge
{
	int from, to, weight, next;
	Edge() {}
	Edge(int f, int t, int w, int n): from(f), to(t), weight(w), next(n) {}
} edges[200010];

/// @brief tot: 当前边数， head: 每个点的第一条边， n: 点数（1 <= n <= 5000）， m: 边数 (1 <= m <= 200000)
int tot, head[5010], n, m;

/// @brief 插入边到图中
/// @param u 起始点
/// @param v 终止点
/// @param w 边权值
void insert(int u, int v, int w)
{
	edges[++tot] = Edge(u, v, w, head[u]);
	head[u] = tot;
}

/// @brief 标记数组和距离数组
bool vis[5010];
int dis[5010];

/// @brief 为下面的 Prim 函数定义节点
struct Node
{
	int u, dis;
	Node() {}
	Node (int _u, int d): u(_u), dis(d) {}
	/// @brief 比较两个Node的大小
	/// @param rhs 右值
	/// @return 如果左值的成员 dis 大于右值，返回 true，否则返回 false
	bool operator<(const Node &rhs) const {
		return dis > rhs.dis;
	}
};

/// @brief Prim算法求最小生成树
/// @return 最小生成树的各边权值之和，如果图不连通，返回 -1
int Prim()
{
	int cnt = 0, ans = 0;
	std::priority_queue<Node> pq;
	pq.push(Node(1, 0));
	memset(vis, false, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	while (!pq.empty())
	{
		if (cnt >= n) {
			break;
		}
		Node tmp = pq.top();
	    pq.pop();
	    if (vis[tmp.u]) {
			continue;
		}
	    vis[tmp.u] = true;
	    ++cnt;
	    ans += tmp.dis;
	    for (int i = head[tmp.u]; i; i = edges[i].next) {
	    	if (edges[i].weight < dis[edges[i].to]) {
	    		dis[edges[i].to] = edges[i].weight;
				pq.push(Node(edges[i].to, edges[i].weight));
	    	}
	    }
	}
	return cnt == n ? ans : -1;
}

/// @brief 主函数读入图，调用 Prim 函数求出最小生成树
/// @return 返回 0 表示程序正常结束
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		insert(u, v, w);
		insert(v, u, w);
	}
	int ans = Prim();
	if (ans == -1) {
		printf("orz\n");
	} else {
		printf("%d\n", ans);
	}
	return 0;
}

吸氧结果

不吸氧结果

是不能用 Prim 只能写 Kruskal, 还是我写错了?
不要上来只给个 Kruskal