mst

Thuật toán Kruskal tìm cây khung nhỏ nhì

nhannguyen95 Algorithm, codemau ,

Code C++:
Độ phức tạp: O(VE)

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <set>
using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int oo = 1e10;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ii> edge;

int n, m, lab[1005];
vector<edge> edges, mst_edges;

int root(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = root(lab[u]);
}

void merge(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}

ll scan_edges(int _u = 0, int _v = 0) {
    memset(lab, -1, sizeof lab);
    
    ll min_cost = 0;
    for(auto e : edges) {
        int u = e.se.fi;
        int v = e.se.se;
        ll w = e.fi;
        if (u == _u && v == _v) continue;
        if (root(u) != root(v)) {
            merge(u, v);
            min_cost += w;
            if (_u == _v) mst_edges.pb(e);
        }
    }
    
    set<int> roots;
    for(int u = 1; u <= n; u++) roots.insert(root(u));
    if (roots.size() != 1) return oo;
    return min_cost;
}

int main() {
    
    // reset
    edges.clear(); mst_edges.clear();
    memset(lab, -1, sizeof lab);
    
    // input
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        edges.pb(mp(w, mp(u, v)));
    }
    
    // modify Kruskal
    sort(edges.begin(), edges.end());
    
    cout << "MST: " << scan_edges() << '\n';
    ll mincost2 = oo;
    for(edge e : mst_edges)
        mincost2 = min(mincost2, scan_edges(e.se.fi, e.se.se));
    cout << "MST2: " << mincost2;
    
    return 0;
}

Input:

5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

Output:

MST: 110
MST2: 121

Happy coding,