【小码匠自习室】最小生成树(kruskal)完结撒花

2023-03-06 14:31:17 浏览数 (1)

最小生成树

  • Prim:算法思路OK,但没刷对应的题目
  • kruskal:打了几个板子题目

今晚上有手撸了下板子代码,使用优先队列做了优化,提交上去,性能提升不明显,有些小郁闷。。。

明天打算开始先学习强连通【Tarjan】,把这些基础算法学完了,在强化刷题。

题目

  • P1546 [USACO3.1]最短网络 Agri-Net
    • https://www.luogu.com.cn/problem/P1546

小码匠

代码
代码语言:javascript复制
#include <bits/stdc  .h>
using namespace std;
#define endl 'n';

struct edge {
    int weight;
    int from;
    int to;
};

struct cmp {
    bool operator() (const edge &a, const edge &b) {
        return a.weight > b.weight;
    }
};

struct UF {
    vector<int> fa;

    UF (int n) :
        fa(n) {}

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

    int find(int a) {
        if (a != fa[a]) {
            fa[a] = find(fa[a]);
        }
        return fa[a];
    }

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

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
};

void best_coder() {
    int n;
    cin >> n;
    priority_queue <edge, vector<edge>, cmp> g;
    UF uf(n);
    uf.initialize(n);
    for (int i = 0; i < n;   i) {
        for (int j = 0; j < n;   j) {
            int a;
            cin >> a;
            if (j <= i) {
                continue;
            }
            g.push({a, i, j});
        }
    }
    int ans = 0;
    while (!g.empty()) {
        int a = g.top().from;
        int b = g.top().to;
        if (uf.is_same(a, b)) {
            g.pop();
            continue;
        }
        uf.unite(a, b);
        ans  = g.top().weight;
        g.pop();
    }
    cout << ans;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

0 人点赞