Prim算法

2024-08-14

采用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;
}