Learning Algorithms

アルゴリズムの勉強メモ

Atcoder ARC #029 C. 高橋くんと国家

Atcoder ARC #029 C. 高橋くんと国家

C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder

ある無向グラフが与えられる。その各辺について、それを舗装するコストと、各都市についてそこに交易所を設置するコストが与えられている。すべての都市について、その都市に交易所があるか、または舗装された道のみを経由して交易所がある都市にいけるうようにするための最小コストを求める問題。まずD: 浮気予防 - AtCoder Beginner Contest 010 | AtCoderの発想に少し近いが、2つの操作を別々に考えることが難しいときは、それらを同一のものとして考えられるようにグラフを変形することが有効な場合がある。舗装の操作は、ある2つの部分を連結にしていく操作であり、それを最小にしていきたいとなると、最小全域木アルゴリズムとそっくりであることに気づく。そこで、ある都市に交易所を設置する操作を、その都市と、交易所を表す新たな頂点Xをその設置コストでつなぐという操作に置き換えると、同様の操作として扱える。最小全域木アルゴリズムはUnionFindで実装した。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int x; scanf("%d", &x); return x; }
long long lin() { long long x; scanf("%lld", &x); return x; }

#define int long long

struct UnionFind {
        vector<int> par;
        UnionFind(int n) : par(n) { for (int i = 0; i < n; i++) par[i] = i; }
        int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
        bool same(int x, int y) { return find(x) == find(y); }
        void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; par[x] = y; }
};

signed main() { 
        int n, m;
        cin >> n >> m;
        vector<pair<int, pair<int, int>>> e;
        rep(i, n) {
                int a;
                cin >> a;
                e.push_back(make_pair(a, make_pair(0, i + 1)));  //交易所設置のコストaで、各頂点を頂点0とつなぐ
        }
        rep(i, m) {
                int a, b, c;
                cin >> a >> b >> c;
                e.push_back(make_pair(c, make_pair(a, b)));
        }
        sort(all(e));
        UnionFind uf(n + 10);
        int ans = 0;
        for (auto v : e) {
                int s = v.second.first;
                int t = v.second.second;
                if (!uf.same(s, t)) {
                        uf.unite(s, t);
                        ans += v.first;
                }
        }
        cout << ans << endl;
        return 0;
}