C++の練習を兼ねて, AtCoder Beginner Contest 270 の 問題F (Transportation) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 270 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
// 解き直し. // https://atcoder.jp/contests/abc270/editorial/4879 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using T3 = tuple<LL, int, int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define all(x) x.begin(), x.end() // https://github.com/atcoder/live_library/blob/master/uf.cpp // UnionFind // coding: https://youtu.be/TdR816rqc3s?t=726 // comment: https://youtu.be/TdR816rqc3s?t=6822 // -> 一部改変. struct UnionFind{ vi d; UnionFind(int n = 0): d(n, -1) {} int find(int x){ return (d[x] < 0) ? x : (d[x] = find(d[x])); } bool unite(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(d[x] > d[y]) swap(x, y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -d[find(x)]; } }; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); // 1-1. 空港. vector<T3> tx; rep(i, N){ LL x; scanf("%lld", &x); tx.emplace_back(x, i, N); } // 1-2. 港. vector<T3> ty; rep(i, N){ LL y; scanf("%lld", &y); ty.emplace_back(y, i, N + 1); } // 1-3. 道路. vector<T3> tz; rep(i, M){ int a, b; LL z; scanf("%d %d %lld", &a, &b, &z); --a, --b; tz.emplace_back(z, a, b); } // 2. 最小全域木(Kruskal's Algorithm) の 構築. // 競プロ典型 90 問 (049 - Flip Digits 2) // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp // -> 空港, 港 を 含む, 含まないで, 4 通り を 確認. LL ans = 202020202020202020; rep(i, 2){ rep(j, 2){ // 候補となる辺. vector<T3> t = tz; // 空港あり. if(i) t.insert(t.end(), all(tx)); // 港あり. if(j) t.insert(t.end(), all(ty)); // sort. sort(all(t)); // グラフ構築. UnionFind uf(N + 3); LL cost = 0; rep(k, t.size()){ // グラフ情報. int u = get<1>(t[k]); // 頂点. int v = get<2>(t[k]); // 頂点. LL c = get<0>(t[k]); // コスト. // 最小全域木を構成する辺の追加. if(!uf.same(u, v)){ uf.unite(u, v); cost += c; } } // 頂点 1 ～ 頂点 N が, 同じ連結成分に含まれるか？ bool ok = true; int g = uf.find(0); repx(k, 1, N) if(g != uf.find(k)) ok = false; // 最小値更新. if(ok) ans = min(ans, cost); } } // 3. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
[入力例] 4 2 1 20 4 7 20 2 20 3 1 3 5 1 4 6 [出力例] 16 ※AtCoderテストケースより [入力例] 3 1 1 1 1 10 10 10 1 2 100 [出力例] 3 ※AtCoderテストケースより [入力例] 7 8 35 29 36 88 58 15 25 99 7 49 61 67 4 57 2 3 3 2 5 36 2 6 89 1 6 24 5 7 55 1 3 71 3 4 94 5 6 21 [出力例] 160 ※AtCoderテストケースより [入力例] 5 5 5 7 8 10 12 7 1 13 11 6 1 2 5 2 3 7 1 3 2 3 4 9 4 5 1 [出力例] 15 [入力例] 7 6 5 6 2 3 8 5 10 8 7 2 1 6 6 6 1 2 3 2 3 1 3 4 7 3 5 9 3 6 2 1 7 4 [出力例] 19 [入力例] 20 25 1020 606 1053 255 1031 592 887 450 875 791 851 1086 655 108 393 650 379 517 111 404 1046 462 208 281 1007 308 856 156 291 864 559 941 1028 128 994 979 1055 989 811 645 1 20 1010 1 16 1347 1 17 1550 2 18 1597 2 19 870 2 20 792 2 3 1639 2 4 1609 3 4 1178 1 3 1537 5 6 1504 7 8 1336 8 11 1160 4 5 1537 9 11 1018 12 13 1244 14 15 1335 16 17 1632 17 18 973 13 18 1296 18 19 1056 10 11 1160 10 12 752 18 19 1492 17 18 1463 [出力例] 10000 |