算法题：最小生成树

问题描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi​,Yi​,Zi​，表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

样例1

输入

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出

7

样例2

输入

6 10
1 2 17
1 5 16
1 6 1
2 6 11
2 3 6
5 6 33
4 6 14
4 5 4
3 4 10
2 4 5

输出

27

数据范围

1≤N≤5000，1≤M≤2×10⁵，1≤Zi≤10⁴。

解决方案

思路

Kruskal or Prim

代码—Kruskal

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    int x, y;
    int w;
};

const int N = 2e5 + 5;

int n, m;
vector<pair<int, int>> g[N];		//下标:连接点 first:被连接的点 second:长度
Node edges[N];

int fa[N];

void init() {
    for (int i = 0; i <= n; ++i) {
        fa[i] = i;
    }
}

int find(int x) {
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}

void join(int x, int y) {
    int a = find(x);
    int b = find(y);
    fa[a] = b;
}

bool cmp(const Node &a,const Node &b) {
    return a.w < b.w;
}

int main() {

    cin >> n >> m;

    init();

    for (int i = 0; i < m; ++i) {
        cin >> edges[i].x >> edges[i].y >> edges[i].w;
        g[edges[i].x].push_back({edges[i].y, edges[i].w});
        g[edges[i].y].push_back({edges[i].x, edges[i].w});
    }

    sort(edges, edges + m, cmp);

    int sum = 0;
    int count = 0;
    for (int i = 0; i < m; ++i) {
        int a = find(edges[i].x);
        int b = find(edges[i].y);

        // 没有环
        if (a != b) {
            count++;
            sum += edges[i].w;
            join(a, b);
        }
    }

    if (count == n - 1)
        cout << sum << endl;
    else
        cout << "orz" << endl;

    return 0;
}

代码—Prim

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Node {
    int x, y;
    int w;
};

const int N = 2e5 + 5;

int n, m;
vector<pair<int, int>> g[N];    //下标:连接点 first:被连接的点 second:长度
Node edges[N];

int vis[N];
int dist[N];    // 点离生成树的最小距离，用来过滤较大距离的线

int main() {

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].x >> edges[i].y >> edges[i].w;
        g[edges[i].x].push_back({edges[i].y, edges[i].w});
        g[edges[i].y].push_back({edges[i].x, edges[i].w});
    }


    int sum = 0;
    int count = 0;


    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;    //first:点离生成树的距离 second:点
    q.push({0, 1});
    while (!q.empty() && count < n) {
        auto [w, point] = q.top();
        q.pop();

        if (vis[point]) continue;
        vis[point] = 1;

        sum += w;
        ++count;

        for (auto item: g[point]) {
            if (dist[item.first] == 0 || dist[item.first] > item.second) {  //松弛操作
                dist[item.first] = item.second;
                q.push({item.second, item.first});
            }
        }
    }

    if (count < n)
        cout << "orz" << endl;
    else
        cout << sum << endl;

    return 0;
}