堆优化Prim 最小生成树模板

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;

const int MAXM = 200005;

int n, m, fir[MAXN], to[MAXM*2], nxt[MAXM*2], w[MAXM*2], cnt, dis[MAXN];

bool vis[MAXN];

#define pii pair<int,int>

#define mp make_pair

priority_queue<pii, vector<pii>, greater<pii> >q;

int MST = 0;

inline void Prim()

{

	int tot = 0;

	memset(dis, 0x3f, sizeof dis);

	q.push(mp(dis[1]=0, 1));

	while(!q.empty())

	{

		int u = q.top().second; q.pop();

		if(vis[u]) continue;

		vis[u] = 1; MST += dis[u]; tot++;

		for(int i = fir[u]; i; i = nxt[i])

			if(!vis[to[i]] && w[i] < dis[to[i]])

				q.push(mp(dis[to[i]]=w[i], to[i]));

	}

	if(tot < n) MST = -1;

}

inline void Add(int u, int v, int wt)

{

	to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; w[cnt] = wt;

}

int main ()

{

	int x, y, z;

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= m; i++)

		scanf("%d%d%d", &x, &y, &z), Add(x, y, z), Add(y, x, z);

	Prim();

	if(~MST) printf("%d\n", MST);

	else puts("orz");

}

巴特西

堆优化Prim 最小生成树模板

最新文章

热门文章

巴特西

堆优化Prim 最小生成树 模板

最新文章

热门文章

堆优化Prim 最小生成树模板