Test/AOJ/Kruskal.test.cpp

• View this file on GitHub
• Last update: 2021-06-18 21:14:35+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

Depends on

• Union-Find (DataStructure/UnionFind.cpp)
• Graph/Kruskal.cpp
• Other/Template.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../Graph/Kruskal.cpp"

int main() {
    cin >> N >> M;
    for(int i = 0;i < M;i++) {
        int s,t;
        long long w;
        cin >> s >> t >> w;
        graph[i] = edge{s,t,w};
    }
    cout << Kruskal() << endl;
}

#line 1 "Test/AOJ/Kruskal.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "DataStructure/UnionFind.cpp"
class UnionFind {
    vector<int> par;
    vector<int> siz;

public:

    UnionFind(int n) {
        par.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++) {
            par[i] = i;
            siz[i] = 1;
        }
    }

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

    void unite(int x,int y) {
        x = find(x);
        y = find(y);
        if(x == y) {
            return;
        }
        if(siz[x] < siz[y]) {
            swap(x,y);
        }
        par[y] = x;
        siz[x] += siz[y];
    }

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

    int size(int x) {
        return siz[find(x)];
    }
};
#line 2 "Graph/Kruskal.cpp"

struct edge {
    int u,v;
    long long cost;

    bool operator<(const edge& b) const {
        return cost < b.cost;
    }
};

int N,M;
edge graph[200010];

long long Kruskal() {
    sort(graph,graph + M);
    UnionFind uf(N);
    long long ret = 0;
    for(int i = 0;i < M;i++) {
        edge e = graph[i];
        if(!uf.same(e.u,e.v)) {
            uf.unite(e.u,e.v);
            ret += e.cost;
        }
    }
    return ret;
}
#line 8 "Test/AOJ/Kruskal.test.cpp"

int main() {
    cin >> N >> M;
    for(int i = 0;i < M;i++) {
        int s,t;
        long long w;
        cin >> s >> t >> w;
        graph[i] = edge{s,t,w};
    }
    cout << Kruskal() << endl;
}

Back to top page