prim求最小生成树

一直以来只会Kruskal

prim和dijkstra很像

只不过prim维护的是最短的边，而dijkstra维护的是最短的从起点到一个点的路径

同时prim要注意当前拓展的边是没有拓展过的

可以用堆优化

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN =  + ;

const int MAXM = 2e5 + ;

struct Edge{ int to, w, next; };

Edge e[MAXM << ];

int head[MAXN], d[MAXN], vis[MAXN], n, m, tot;

void AddEdge(int from, int to, int w)

{

    e[tot] = Edge{to, w, head[from]};

    head[from] = tot++;

}

void read(int& x)

{

    int f = ; x = ; char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -; ch = getchar(); }

    while(isdigit(ch)) { x = x *  + ch - ''; ch = getchar(); }

    x *= f;

}

void prim()

{

    vis[] = ;

    _for(i, , n) d[i] = i ==  ?  : 1e9;

    for(int i = head[]; ~i; i = e[i].next)

    {

        int v = e[i].to;

        d[v] = min(d[v], e[i].w);

    }

    int ans = ;

    REP(k, , n)

    {

        int mint = 1e9, id;

        _for(i, , n)

            if(!vis[i] && d[i] < mint)

            {

                mint = d[i];

                id = i;

            }

        ans += mint;

        vis[id] = ;

        for(int i = head[id]; ~i; i = e[i].next)

        {

            int v = e[i].to;

            if(vis[v]) continue;

            d[v] = min(d[v], e[i].w);

        }

    }

    printf("%d\n", ans);

}

int main()

{

    memset(head, -, sizeof(head)); tot = ;

    read(n); read(m);

    _for(i, , m)

    {

        int u, v, w;

        read(u); read(v); read(w);

        AddEdge(u, v, w);

        AddEdge(v, u, w);

    }

    prim();

    return ;

}

堆优化版本

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN =  + ;

const int MAXM = 2e5 + ;

struct Edge{ int to, w, next; };

Edge e[MAXM << ];

int head[MAXN], d[MAXN], vis[MAXN], n, m, tot;

void AddEdge(int from, int to, int w)

{

    e[tot] = Edge{to, w, head[from]};

    head[from] = tot++;

}

void read(int& x)

{

    int f = ; x = ; char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -; ch = getchar(); }

    while(isdigit(ch)) { x = x *  + ch - ''; ch = getchar(); }

    x *= f;

}

struct node

{

    int id, w;

    bool operator < (const node& rhs) const

    {

        return w > rhs.w;

    }

};

priority_queue<node> q;

void prim()

{

    vis[] = ;

    _for(i, , n) d[i] = i ==  ?  : 1e9;

    for(int i = head[]; ~i; i = e[i].next)

    {

        int v = e[i].to;

        d[v] = min(d[v], e[i].w);

    }

    _for(i, , n) q.push(node{i, d[i]});

    int ans = ;

    REP(k, , n)

    {

        int mint, id;

        while()

        {

            node x = q.top(); q.pop();

            if(vis[x.id]) continue;

            id = x.id, mint = x.w;

            break;

        }

        ans += mint;

        vis[id] = ;

        for(int i = head[id]; ~i; i = e[i].next)

        {

            int v = e[i].to;

            if(vis[v]) continue;

            if(d[v] > e[i].w)

            {

                d[v] = e[i].w;

                q.push(node{v, d[v]});

            }

        }

    }

    printf("%d\n", ans);

}

int main()

{

    memset(head, -, sizeof(head)); tot = ;

    read(n); read(m);

    _for(i, , m)

    {

        int u, v, w;

        read(u); read(v); read(w);

        AddEdge(u, v, w);

        AddEdge(v, u, w);

    }

    prim();

    return ;

}