C++の練習を兼ねて, 全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019 の 問題E (Weights on Vertices and Edges) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. Union-Find木 の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 本問の実装に色々苦労したものの, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019 解説をご覧下さい.
■C++版プログラム(問題E/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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 |
// 一部ロジック修正して, 再提出. // 解き直し. // https://img.atcoder.jp/nikkei2019-qual/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<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 pb push_back #define a first #define b second #define all(x) x.begin(), x.end() struct edge{ int n; // 次の頂点. LL w; // 重み. }; struct info{ int u, v; // 頂点. LL w; // 重み. bool operator < (const info &E) const { return w > E.w; } }; LL X[101010]; // 各頂点の重み. vector<edge> G[101010]; // グラフ. // 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{ vector<int> d; vector<LL> weights; UnionFind(int n = 0): d(n, -1), weights(n, 0) {} void setWeights(int x, LL w){ weights[x] = w; } int find(int x){ if(d[x] < 0) return x; return 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; weights[x] += weights[y]; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -d[find(x)]; } LL sum(int x){ return weights[find(x)]; } }; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld", &X[i]); vector<info> v; rep(i, M){ int a, b; LL w; scanf("%d %d %lld", &a, &b, &w); a--, b--; // 辺情報を保存. if(a > b) swap(a, b); info e; e.u = a; e.v = b; e.w = w; v.pb(e); // グラフ. edge e1, e2; e1.n = b, e2.n = a; e1.w = w, e2.w = w; G[a].pb(e1); G[b].pb(e2); } // 2. sort. sort(all(v)); // 降順sort. // puts("--- v start ---"); // for(auto &e : v) printf("%d %d %lld\n", e.u, e.v, e.w); // puts("---- v end ----"); // 3. 辺の重みが小さい順に, 辺を追加. UnionFind uf(N); rep(i, N) uf.setWeights(i, X[i]); set<P> res; // 残す辺(候補). repr(i, v.size() - 1, 0){ info e = v[i]; int u = e.u; int v = e.v; LL w = e.w; if(u > v) swap(u, v); if(!uf.same(u, v)) uf.unite(u, v); int r = uf.find(u); if(uf.sum(r) >= w) res.insert({u, v}); } // puts("--- res start ---"); // for(auto &e : res) printf("%d %d\n", e.a, e.b); // puts("---- res end ----"); // 4. 辺の重みが大きい順に, 残す辺をチェック. set<P> eRes; // 残す辺. set<P> memo; // 訪問済みフラグ. function<void(int, LL)> f = [&](int sv, LL sw) { // 1. 初期化. priority_queue<pair<LL, int>> pq; // 2. 始点設定. pq.push({sw, sv}); // 3. キュー pq が 空になるまで, 探索. while(!pq.empty()){ // 4. 探索を継続するために, 頂点を取得. LL cw = pq.top().a; int cv = pq.top().b; pq.pop(); // 5. 各隣接する頂点について確認. for(auto &ne : G[cv]){ LL nw = ne.w; int nv = ne.n; int a = min(cv, nv), b = max(cv, nv); // 6. 辺を保存, 訪問済みフラグ設定. // nw <= cw でなく nw <= sw に ロジック修正. // ex. // 辺(辺の重み)について, // e1(16) -> e2(1) -> e3(8) -> e4(20) の 場合に, e1, e2, e3 までを取得する必要がある. // 実際, 取得される辺について, 以下のように, 異なる結果となる. // nw <= cw の 場合: e1, e2 // nw <= sw の 場合: e1, e2, e3 if(!memo.count({a, b}) && nw <= sw) eRes.insert({a, b}), pq.push({nw, nv}); memo.insert({a, b}); } } }; rep(i, v.size()){ // 辺 e を 取得. info e = v[i]; int u = e.u; int v = e.v; LL w = e.w; if(u > v) swap(u, v); // 今回の結果から, 残す辺に含まれるか? // -> 重みが, 辺 e 以下の辺も, 辿っていける場合は, すべて残す. if(res.count({u, v})) f(u, w); } // for(auto &p : eRes) printf("%d %d\n", p.a, p.b); // 5. 残す辺数を計算. int ans = M - eRes.size(); // 6. 出力. 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 |
[入力例] 4 4 2 3 5 7 1 2 7 1 3 9 2 3 12 3 4 18 [出力例] 2 ※AtCoderテストケースより [入力例] 6 10 4 4 1 1 1 7 3 5 19 2 5 20 4 5 8 1 6 16 2 3 9 3 6 16 3 4 1 2 6 20 2 4 19 1 2 9 [出力例] 4 ※AtCoderテストケースより [入力例] 10 9 81 16 73 7 2 61 86 38 90 28 6 8 725 3 10 12 1 4 558 4 9 615 5 6 942 8 9 918 2 7 720 4 7 292 7 10 414 [出力例] 8 ※AtCoderテストケースより [入力例] 7 11 5 1 1 3 1 2 2 1 7 11 7 2 19 1 2 8 5 2 23 1 5 17 2 3 10 2 4 7 4 5 16 4 6 13 6 3 2 1 4 18 [出力例] 5 [入力例] 10 8 1 1 2 5 7 2 3 1 1 1 6 7 4 7 8 7 1 3 10 1 2 19 2 10 2 3 9 17 9 4 3 3 5 8 [出力例] 3 |
■参照サイト
全国統一プログラミング王決定戦予選/NIKKEI ProgrammingContest 2019
Union-Find木