H-prim 最小生成树

知道了prim最小生成树算法，我们发现每次找距离最小的点的操作和dijkstra算法中的操作很像，所以我们考虑是否可以将迪杰的优化套到prim上，也即用优先队列

时间复杂度大概是O(mlogm)

例题：洛谷 P3366 【模板】最小生成树

#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#pragma GCC target("avx") 
#pragma GCC optimize (2)
#define INF 0x7fffffff
#define forup(i, l, r) for(int i = l; i <= r; i++)
using namespace std;
const int N = 5005;
vector<pair<int, int>> e[N];
priority_queue<pair<int, int>> q;//min_dis from the tree and corresponding node 
int min_d[N];//min_dis of node i from the tree
bool vis[N];//if in the tree
int n, m;
int sum;

bool prim(int s)//堆优化的适合稀疏图，复杂度O(mlogm)，不优化是O(n^2)
{
	forup(i, 1, n) min_d[i] = INF;//INF == (1 << 31) - 1
	q.push({0, s});
	min_d[s] = 0;
	int cnt = 0;
	
	while(!q.empty())
	{
		int u = q.top().second; q.pop();
		
		if(vis[u]) continue;
		else vis[u] = true;
		
		sum += min_d[u];
		
		if(min_d[u] != INF) cnt++;//如果不连通，不更新，不计数 
		
		for(auto x: e[u])
		{
			int v = x.first, w = x.second;
			if(min_d[v] > w)
			{
				min_d[v] = w;
				q.push({-w, v});
			}
		}
		
		if(cnt == n) return 1;
	}
	return cnt == n;
} 
int main()
{
	cin>>n>>m;
	forup(i, 1, m)
	{
		int u, v, w;
		cin>>u>>v>>w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	if(prim(1))
	{
		cout<<sum;
	}
	else cout<<"orz";
	return 0;
}