采用Prim算法,求无向图的最小生成树
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 5005, M = 200001;
struct edge
{
int to, w;
edge(int a, int b) { to = a, w = b; }
};
vector<edge> G[M];
struct node
{
int id, dis;
node(int a, int b) { id = a, dis = b; }
bool operator<(const node &u) const { return dis > u.dis; }
};
int n, m;
bool done[N];
void prim()
{
int s = 1;
for (int i = 1; i <= N; i++)
done[i] = false;
priority_queue<node> q;
q.push(node(s, 0));
int ans = 0, cnt = 0;
while (!q.empty())
{
node u = q.top();
q.pop();
if (done[u.id])
continue;
done[u.id] = true;
ans += u.dis;
cnt++;
for (int i = 0; i < G[u.id].size(); i++)
{
edge y = G[u.id][i];
if (done[y.to])
continue;
q.push(node(y.to, y.w));
}
}
if (cnt == n)
cout << ans;
else
cout << "orz";
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b, w;
cin >> a >> b >> w;
G[a].push_back(edge(b, w));
G[b].push_back(edge(a, w));
}
prim();
return 0;
}