C/C++：Prim+堆优化最小生成树模板

洛谷：P3366 ，和Dijkstra堆优化模板差不多

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入输出格式

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例

输入样例#1：

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出样例#1：

7

Prim+堆优化模板

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

static const int MAXN = 5005;
static const int MAXM = 200005;

struct node {
	int next,to,dis;
};

node e[MAXM << 1];

int head[MAXN],vis[MAXN],dis[MAXN];
int n,m,cnt,num,sum;

inline void add(int from,int to,int dis) {
	e[++cnt].next = head[from];
	e[cnt].to = to;
	e[cnt].dis = dis;
	head[from] = cnt;
}

void Prim_Heap(int s) {
	memset(dis,0x3f,sizeof dis);
	memset(vis,false,sizeof vis);
	priority_queue <pair <int ,int >, vector < pair <int ,int > >, greater < pair <int ,int > > > Q;
	dis[s] = 0;
	Q.push(make_pair(0,s));
	while(!Q.empty()) {
		int u = Q.top().second;
		int d = Q.top().first;
		Q.pop();
		if(vis[u]) continue;
		num++;
		sum += d; 
		vis[u] = true;
		for(int i = head[u];i;i = e[i].next) {
			int v = e[i].to;
			if(dis[v] > e[i].dis) {
				dis[v] = e[i].dis;
				Q.push(make_pair(dis[v],v));
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;++i) {
		int from,to,dis;
		cin >> from >> to >> dis;
		add(from,to,dis);
		add(to,from,dis);
	}
	Prim_Heap(1);
	if(num == n) printf("%d\n",sum);
	else puts("orz");
	return 0;
}