堆优化Prim

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int, int> P;
const int N = 510, M = 1e5 + 10, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
int n, m;
bool used[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<P, vector<P>, greater<P>> heap;
    int res = 0, cnt = 0;
    dist[1] = 0, heap.push({0, 1});

    while(heap.size())
    {
        auto pp = heap.top(); heap.pop();
        int t = pp.second;
        if(used[t]) continue;

        used[t] = true;
        res += dist[t];
        cnt++;
        for(int i = 1; i <= n; i++)
            if(!used[i] && dist[i] > g[t][i])
            {
                dist[i] = g[t][i];
                heap.push({dist[i], i});
            }
    }
    if(cnt != n) return INF;
    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);
    scanf("%d%d", &n, &m);
    int u, v, w;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = g[v][u] = min(g[u][v] , w);
    }
    int t = prim();
    if(t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

朴素Prim

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 1e5 + 10, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
int n, m;
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    dist[1] = 0;
    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if(dist[t] == INF) return INF;
        st[t] = true;
        res += dist[t];

        for(int j = 1; j <= n; j++)
            if(!st[j] && dist[j] > g[t][j]) dist[j] = g[t][j];
    }
    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);
    scanf("%d%d", &n, &m);
    int u, v, w;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = g[v][u] = min(g[u][v] , w);
    }
    int t = prim();
    if(t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}