kruskal

#include <bits/stdc++.h>//kruskal算法
using namespace std;
#define int long long
int n, m, ans = 0;
int u, v, cnt = 0;
struct edge
{
    int x, y, val;
} a[200010];
int f[200010];
int find(int x) {
    if (f[x] == x)return x;
    return f[x] = find(f[x]);
}
void kruskal() {
    for (int i = 1; i <= m; i++) {
        u = find(a[i].x);
        v = find(a[i].y);
        if (u == v)
            continue;
        ans += a[i].val;
        f[u] = v;
        if (++cnt == n - 1)
            break;
    }
}
int cmp(edge a, edge b) {
    return a.val < b.val;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 1; i <= m; i++)
        cin >> a[i].x >> a[i].y >> a[i].val;
    sort(a + 1, a + 1 + m, cmp);
    kruskal();
    if (cnt != n - 1)
        cout << "orz" << endl;
    else
        cout << ans << endl;
}

Prim 算法

邻接表

constexpr int N = 5010;
int n, m, a, b, c, ans, cnt;
struct edge { int v, w; };
vector<edge> e[N];
int d[N], vis[N];
priority_queue<pair<int, int>> q;

bool prim(int s) {
    for (int i = 0;i <= n;i++) d[i] = inf;
    d[s] = 0; q.push({0,s});
    while (q.size()) {
        int u = q.top().second; q.pop();
        if (vis[u])continue;//再出队跳过
        vis[u] = 1;//标记u已出队
        ans += d[u]; cnt++;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (d[v] > w) {
                d[v] = w;
                q.push({-d[v],v});//大根堆
            }
        }
    }
    return cnt == n;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        e[a].push_back({b,c});
        e[b].push_back({a,c});
    }
    if (!prim(1))puts("orz");
    else printf("%d\n", ans);
    return 0;
}

链式前向星

#include<bits/stdc++.h>//prim堆优化版
using namespace std;
typedef pair<int, int> PII; //<距离，顶点>
priority_queue<PII, vector<PII>, greater<PII>> heap;
const int N = 5010, M = 2e5 + 10; //无向图，边数要乘2
int h[N], e[M], w[M], ne[M], idx;
int dis[N];
bool vis[N]; //判断是否已经加入生成树的集合
int n, m;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int prim() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    heap.push({dis[1], 1}); //本来还应该剩下的顶点都放进去，然后进行更新就行了，但是stl中的堆不能实现按关键字更新，
    int num = n, res = 0;   //用插入代替更新，所以，剩下的点就不放入了，更新到时再放入
    while (heap.size() && num) { //这里为什么这么写,原因同dijkstra
        auto t = heap.top();
        heap.pop();
        int v = t.second, d = t.first;
        //"此时取出的d必不可能是INF，因为前面加入堆的原因就是它被更新过" 
        if (vis[v]) continue; //如果v已经在生成树中了，本次循环无效，开始下一次，后面不再执行
        vis[v] = true, res += d, num--;                                                      //否则，加入生成树
        //修改未在生成树中的点到集合的最短距离
        for (int i = h[v]; i != -1; i = ne[i]) {
            int j = e[i]; // v->e[i]的边,权值为w[i]
            if (!vis[j] && dis[j] > w[i])
                dis[j] = w[i], heap.push({dis[j], j});
        }
        //"只有当v到其它顶点可达或者距离更小，才会更新，因此每次取出的d都不是INF,当都不可达时，队列就为null了"
    }
    //"判断是因为什么原因退出？是因为堆空，还是有效循环num次完了"
    //"因为堆空退出说明图是非连通图，存在不可达点,此时num>0;但是如果num==0，说明已经得到了生成树。" 
    return num ? -1 : res;
}

int main() {
    memset(h, -1, sizeof h);
    //"切记，邻接表存储时要初始化h数组" 
    scanf("%d%d", &n, &m);
    int a, b, c;
    while (m--) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    int t = prim();
    t == -1 ? puts("impossible") : printf("%d", t);

    return 0;
}

朴素的 prim 算法 $O(n^2)$

#include<bits/stdc++.h>//朴素的prim算法
using namespace std;
const int N = 5010, INF = 0x3f3f3f3f;
int g[N][N];
int dis[N]; 
bool vis[N];
int n, m;

int prim()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0; //随便从一个起点开始
    int num = n, res = 0;
    while (num--)
    {              //对于连通图，必须要循环n次才能到所有顶点，获得最小生成树，非连通图会中途break
        int t = 0; //结点是从1开始的，t=0，此时说明还没开始待选
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && (!t || dis[i] < dis[t]))
                t = i;
        }
        if (dis[t] == INF)
            return -1; //存在顶点不可达，说明是不存在生成树
        vis[t] = true; //否则，顶点t加入集合
        res += dis[t]; //计算生成树的代价,第一次循环时必为事先初始化的1号顶点，dis为0，相当于不加
        //开始更新到集合(顶点t)的距离
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && dis[i] > g[t][i])
                dis[i] = g[t][i];
            //"只更新不在集合中的点，维护dis数组的含义，所以dis[t]不会被更新，就算自环是负值也不会被更新。"
        }
    }
    return res; //返回最小生成树的代价
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    int a, b, c;
    while (m--)
    {
        scanf("%d%d%d", &a, &b, &c);         
        g[a][b] = g[b][a] = min(g[a][b], c); 
    }
    int t = prim();
    t == -1 ? puts("orz") : printf("%d", t);

    return 0;
}