C++の練習を兼ねて, AtCoder Regular Contest 165 の 問題C (Social Distance on Graph) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説の二部グラフを使った考え方で解ける点が, 興味深く思った.
3. Union-Find木 の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 165 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://atcoder.jp/contests/arc165/editorial/7137 // C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using T3 = tuple<int, int, int>; using vi = vector<int>; using vp = vector<P>; using vvp = vector<vp>; using vt = vector<T3>; #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 a first #define b second #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); vt t; vvp G(N); rep(i, M){ int a, b, w; scanf("%d %d %d", &a, &b, &w); --a; --b; G[a].emplace_back(P{w, b}); G[b].emplace_back(P{w, a}); t.emplace_back(T3{w, a, b}); } // 2. sort. sort(all(t)); rep(i, N) sort(all(G[i])); // 3. 2本の辺を用いるパスの重みの最小値は？ int ans = 2020202020; rep(i, N) if(G[i].size() >= 2) ans = min(ans, G[i][0].a + G[i][1].a); // 4. グラフが初めて二部グラフでなくなる辺の重みは？ // -> 最小全域木(Kruskal's Algorithm) の アルゴリズム を 流用. // 競プロ典型 90 問 (049 - Flip Digits 2) // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp UnionFind uf(2 * N + 4); rep(i, t.size()){ // 4-1. グラフ情報. int w = get<0>(t[i]); int a = get<1>(t[i]); int b = get<2>(t[i]); // 4-2. 辺 を 追加. uf.unite(2 * a, 2 * b + 1); uf.unite(2 * b, 2 * a + 1); // 4-3. 連結か？ // 二部グラフで無くなった場合に, 連結と判定される. if(uf.same(2 * a, 2 * a + 1)){ ans = min(ans, w); break; } } // 5. 出力. printf("%d\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 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
[入力例] 3 3 1 2 5 2 3 6 1 3 12 [出力例] 11 ※AtCoderのテストケースより [入力例] 10 20 7 10 982219000 3 10 968366179 2 4 992330437 5 6 984414664 2 8 897295423 7 9 155604979 6 8 958833005 2 3 973209957 3 7 985173062 6 10 963895817 2 10 986243534 4 5 721724794 1 3 657562445 1 6 566370694 1 4 988050146 1 9 967817807 4 9 796531581 5 9 983960054 1 10 964450079 8 9 959369491 [出力例] 952136560 ※AtCoderのテストケースより [入力例] 10 20 5 6 871895994 8 10 873709822 3 5 454175869 6 10 980782191 2 6 901290987 1 8 298092290 4 8 693116157 4 5 947939338 7 8 934395075 7 9 759563833 5 8 779870031 4 6 919637355 2 9 822858749 4 10 855497285 3 7 954942051 1 2 950411658 4 7 665939990 3 4 634533617 5 7 908372507 1 9 591466693 [出力例] 759563833 ※AtCoderのテストケースより [入力例] 5 7 1 2 3 1 3 7 1 5 4 2 5 9 3 4 8 2 4 7 3 5 10 [出力例] 7 [入力例] 12 11 1 2 8 1 5 3 1 4 7 2 3 12 2 7 5 3 10 8 4 8 5 4 6 11 6 9 3 7 11 8 10 12 13 [出力例] 10 [入力例] 16 20 1 2 8 1 4 7 1 15 8 2 3 12 2 4 18 2 6 6 2 9 20 3 7 12 3 9 10 4 7 7 4 8 12 5 8 7 5 13 12 6 14 18 7 10 30 7 11 11 8 12 10 9 10 6 11 12 5 15 16 27 [出力例] 12 |