堆优化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");
}
上一篇:bzoj1601 / P1550 [USACO08OCT]打井Watering Hole(堆优化prim)


下一篇:关于一个sql的优化分析