QUPC G. Tapu & Tapi 2
最終的にたぷちゃんとたぴちゃんの両方が存在するような連結成分が存在しなければOKなのでそれ以外の3つの状態をすべて持つことにします。
$dp1[u] :=$ $u$ を含む連結成分にたぷちゃんもたぴちゃんも存在しないもので有効な状態にする最小コスト
$dp2[u] :=$ $u$ を含む連結成分にたぷちゃんのみが存在するもので有効な状態にする最小コスト
$dp3[u] :=$ $u$ を含む連結成分にたぴちゃんのみが存在するもので有効な状態にする最小コスト
この問題では遷移のための他の状態は何も必要なくて以下のように遷移できてこの問題は解けました。$v$ は $u$ の子ども、 $c$ は $u, v$ 間のコストです。
$dp1[u] = \sum min(dp1[v], min(dp2[v], dp3[v]) + c)$
$dp2[u] = \sum min(min(dp1[v], dp2[v]), dp3[v] + c)$
$dp3[u] = \sum min(min(dp1[v], dp3[v]), dp2[v] + c)$
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++) using namespace std; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; int main() { int n, x, y; scanf("%d%d%d", &n, &x, &y); vector<vector<pair<int, int>>> g(n); rep(i, n - 1) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a --, b --; g[a].push_back({b, c}); g[b].push_back({a, c}); } vector<int> tg(n); rep(i, x) { int a; scanf("%d", &a); a --; tg[a] = 1; } rep(i, y) { int a; scanf("%d", &a); a --; tg[a] = 2; } vector<long long> dp1(n), dp2(n), dp3(n); function<void (int, int)> dfs = [&](int u, int prev) { if (tg[u] != 0) dp1[u] = INFL; if (tg[u] == 1) dp2[u] = INFL; if (tg[u] == 2) dp3[u] = INFL; for (auto e : g[u]) { int v = e.first; if (v == prev) continue; int c = e.second; dfs(v, u); if (dp1[u] != INFL) dp1[u] += min(dp1[v], min(dp2[v], dp3[v]) + c); if (dp2[u] != INFL) dp2[u] += min(min(dp1[v], dp2[v]), dp3[v] + c); if (dp3[u] != INFL) dp3[u] += min(min(dp1[v], dp3[v]), dp2[v] + c); } }; dfs(0, -1); printf("%lld\n", min({dp1[0], dp2[0], dp3[0]})); return 0; }
codeFlyer 参加記
参加しました。
https://beta.atcoder.jp/contests/bitflyer2018-final
開始前、wifiが接続できない感じで不安でしたが、近くにnuipさんがいたおかげで安心してコンテストに臨めました。
コンテスト中、ほぼすべての時間を使ってFとGを解こうとしました。Fを解くのに1時間かけて、あとはGを解こうとしていましたが、わからず。
Gを解いてる最中、気分転換に解法がすぐに生えたAとCを通しました。BとEにはhogeというテキストを投げました。DとHは読んでいません。
終わったあとは主にminaminaoさん、pekempeyさん、sugimさんと話していました。みなさんいい人でとても楽しかったです。minamiさんは普通に仲いいです。pekempeyさんは、読み方がペケムペイであることが判明しました。sugimさんは優しくてイケメンでした。他に話してくださった方々も含め、ありがとうございました！
オンサイトのコンテストはやっぱり楽しいので、また次回もがんばりたいと思います。
ICPC 2018 国内予選参加記
今年も神戸大学のチームとして、アルゴリズムのプロkimiyukiさん、マラソンマッチのプロkurenai3110さん、えんぴつ画を描くのが上手な僕KokiYmgch、の3人で出ました。
僕はいま東京に住んでいるので朝7時に出発して神戸大学に向かいます。ワクワク！
11時半には神戸に着いてのんびり準備する予定でしたが、関西の天気がアで、なぜか16時に着きました。冷えました。
僕の担当はABCDEF以外で、G問題が構文解析っぽい何か、H問題が木だったので、ずっとH問題をやっていました。
解けません。激冷えして終わりました。
帰りの新幹線もダメで、帰ることもできません。家もないのでこのままストリートえんぴつ画家として生きていきます。
アジア地区大会もよろしくお願いします。
全方位木dp
全方位木dpについてです。
基本的にここにまとまっていて、僕自身もこの記事から学びました。本記事では、これよりもわかりやすく簡潔な実装します。
名前が大げさですが、普通の木dpを少し拡張するだけです。上のサイトの例題 $1$ にもありますが、次のような問題を考えます。
木の各頂点について、その頂点から伸びる各辺それぞれに対して、その辺を使って移動できる最も遠い距離を求めて下さい。$n \leq 10^6$
まずある頂点を根に固定して、普通の木dpをすると、各頂点についてその頂点から子の方向に向かって伸びる各辺に対する答えはすぐに計算できます。
dを求める答え、farを子の中で最も遠い頂点までの距離の最大値とすると、以下のように書けます。
vector<vector<pair<int, int>>> d(n); //(距離, 行き先) vector<int> far(n); function<void (int, int)> dfs = [&](int u, int prev) { for (auto v : g[u]) if (v != prev) { dfs(v, u); far[u] = max(far[u], far[v] + 1); d[u].push_back({far[v] + 1, v}); } }; dfs(0, -1);
さて、あとは各頂点についてその親方向に伸びる辺の答えがわかればよさそうです。そこで、以下のように頂点 $u$ についてはすべての答えが求められている（赤いところが行き先）として、これから頂点 $v$ の答えを求めたいとします。
もし $u$ の行き先の中で最も遠い行き先が $v$ である場合は、明らかにそれを $v$ の答えに含めてはいけないので、$u$ の行き先の中で二番目に大きいものを取れば良いです。逆に $u$ の最大値が $v$ の方向ではない方向でとれるなら、それは $v$ から見てもやはり最大であるはずです。
それをそのまま実装すると以下のようになります。根だけは距離のソートを一番最初にしています。
sort(d[0].rbegin(), d[0].rend()); function<void (int, int)> dfs2 = [&](int u, int prev) { for (auto v : g[u]) if (v != prev) { if (d[u][0].second == v) { //最大値をとる行き先を見る d[v].push_back({((int) d[u].size() == 1 ? 0 : d[u][1].first) + 1, u}); } else { d[v].push_back({d[u][0].first + 1, u}); } sort(d[v].rbegin(), d[v].rend()); dfs2(v, u); } }; dfs2(0, -1);
((int) d[u].size() == 1 ? 0 : d[u][1].first)のところは、次のような根であって、そこから二番目の距離が存在しないケースに対処しています。
この発想さえわかっていれば、いつもの木dpと同じ感覚で全方位木dpも書けるんじゃないかと思います。
練習問題をおいておくのでぜひやってみてください（ただし重いです）。
F - Black Radius
E - 足のばし
木の辺の最大値のダブリング
木上のパスが含む辺の中で、その重みの最大値(最小値)を対数時間で求めるライブラリです。
よく知られたダブリングというテクニックを使っています。ダブリングについてはここでは書きませんが、parmax[k][u] というのは、頂点 $u$ から根に向かってパスを $2^k$ 本辿った時に使う辺の重みの最大値です。
struct LowestCommonAncestorTreeMax { const int LOGM = 30; vector<int> depth, par_w; vector<vector<int>> parent, parmax; LowestCommonAncestorTreeMax(int root, const vector<vector<pair<int, int>>> &g) { int n = g.size(); depth.resize(n); par_w.resize(n); parent.resize(LOGM); parmax.resize(LOGM); for (int i = 0; i < LOGM; i ++) { parent[i].resize(n); parmax[i].resize(n); } function<void (int, int, int)> dfs = [&](int u, int prev, int d) { parent[0][u] = prev; parmax[0][u] = par_w[u]; depth[u] = d; for (auto e : g[u]) { int v = e.first; if (v != prev) { par_w[v] = e.second; dfs(v, u, d + 1); } } }; dfs(root, -1, 0); for (int k = 0; k < LOGM - 1; k ++) { for (int i = 0; i < n; i ++) { if (parent[k][i] < 0) { parent[k + 1][i] = -1; } else { parent[k + 1][i] = parent[k][parent[k][i]]; if (parent[k + 1][i] >= 0) { parmax[k + 1][i] = max(parmax[k][i], parmax[k][parent[k][i]]); } } } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < LOGM; k ++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = LOGM - 1; k >= 0; k --) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } int getmax(int v, int ancestor) { int res = 0; int d = depth[v] - depth[ancestor]; for (int k = 0; k < LOGM; k ++) { if ((d >> k) & 1) { res = max(res, parmax[k][v]); v = parent[k][v]; } } return res; } };
根とする頂点 root 、木の隣接リスト（各辺は(行き先、重み)のペア）gで呼び出して、以下のように使います。
//s-tパス上の辺の重み最大値を求める例 LowestCommonAncestorTreeMax tree(root, g); int lca = tree.lca(s, t); int res = max(tree.getmax(s, lca), tree.getmax(t, lca));
以下の問題で $verify$ しています。
以上です。
二重頂点連結成分分解木
二重頂点連結成分分解木のライブラリです。誰も使わないと思います。
これの続きです。
任意の無向グラフから二重頂点連結成分と関節点を頂点とする木を構築できます。それをやってくれるライブラリです。
//e2i[edge] -> index of the edge //tree index : [0, 1, ..., bc.size() - 1] -> component //tree index : [bc.size(), bc.size() + 1, ..., bc.size() + art.size() - 1] -> articulation //cmp[index of edge] -> index of the node of the contructed tree //cmp_node[index of node] -> -1 if it's not articulation, otherwise index of the node of the constructed tree struct BiconnectedComponentTree { vector<int> ord, low, art, cmp, cmp_node; vector<bool> used; vector<vector<int>> g, tree; vector<vector<pair<int, int>>> bc; vector<pair<int, int>> tmp; map<pair<int, int>, int> e2i; int n, m, k = 0; BiconnectedComponentTree(const vector<vector<int>> &g, const map<pair<int, int>, int> &e2i) : g(g), e2i(e2i) { n = g.size(); m = e2i.size(); cmp_node.resize(n, -1); cmp.resize(m, -1); ord.resize(n, -1); low.resize(n, -1); used.resize(n, false); } void dfs(int u, int prev) { used[u] = true; ord[u] = k ++; low[u] = ord[u]; bool is_art = false; int cnt = 0; for (auto v : g[u]) if (v != prev) { if (ord[v] < ord[u]) { tmp.emplace_back(min(u, v), max(u, v)); } if (!used[v]) { cnt ++; dfs(v, u); low[u] = min(low[u], low[v]); if (prev != -1 && low[v] >= ord[u]) { is_art = true; } if (low[v] >= ord[u]) { bc.push_back({}); while (true) { pair<int, int> e = tmp.back(); bc.back().emplace_back(e); tmp.pop_back(); if (min(u, v) == e.first && max(u, v) == e.second) { break; } } } } else { low[u] = min(low[u], ord[v]); } } if (prev == -1 && cnt > 1) is_art = true; if (is_art) art.push_back(u); } void build() { dfs(0, -1); for (int i = 0; i < (int) bc.size(); i ++) { for (auto e : bc[i]) { cmp[e2i[make_pair(min(e.first, e.second), max(e.first, e.second))]] = i; } } tree.resize(bc.size() + art.size()); for (int i = 0; i < (int) art.size(); i ++) { int j = i + (int) bc.size(); cmp_node[art[i]] = j; int u = art[i]; set<int> tmp; for (auto v : g[u]) { int t = cmp[e2i[make_pair(min(u, v), max(u, v))]]; if (tmp.count(t) == 0) { tmp.insert(t); } } for (auto v : tmp) { tree[j].push_back(v); tree[v].push_back(j); } } } };
使い方は、グラフの隣接リストgと、辺の頂点ペア->辺番号の $map$ であるe2iを以下のように渡すだけです。
BiconnectedComponentTree bct(g, e2i); bct.build();
もとのグラフの辺の $index$ をiとすると、構築された木の対応する頂点番号はcmp[i]です。
また、もとのグラフの頂点の $index$ を iとすると、それが関節点でなければcmp_node[i] = -1であり、関節点である場合は木の対応する頂点番号がcmp_node[i]になります。
二重頂点連結成分分解
二重頂点連結成分分解の実装です。
追記：誤りがあったので大幅に変更しました。
名前が似ていますが、二重辺連結成分分解とは異なります。そちらについてはこの記事をご覧ください。
任意の無向グラフを、その部分グラフであって「その部分グラフにおける関節点」を含まないような構造(二重頂点連結成分)に分解します。
二重頂点連結成分のことをあえて「構造」と書いたのは、頂点が必ず一つの成分に含まれるとは限らないからです。一方各辺は必ず一つの連結成分に属するので、すべての辺集合を、二重頂点連結成分をなす辺集合に分割すると考えることができます。
以下のグラフを二重頂点連結成分分解することを考えてみます。
まず関節点を列挙して、その点の周りでグラフを切ります。
連結成分に注意して、切れ目を適切に繋ぎます。
このギザギザで囲まれた部分が二重頂点連結成分になります。
番号5に含まれる辺集合に間違いがありました。その集合は二つの別の集合に分かれます。
実装は少しややこしいですが、$LowLink$ におけるordとlowを適切に見ながら、閉路ごとに辺集合をまとめていけばよいです。
bcに辺集合のvectorが入ります。tmpにはこれまでに見た辺を一旦格納しています。
struct BiconnectedComponent { vector<int> ord, low; vector<bool> used; vector<vector<int>> g; vector<vector<pair<int, int>>> bc; vector<pair<int, int>> tmp; int n, k = 0; BiconnectedComponent(const vector<vector<int>> &g) : g(g) { n = g.size(); ord.resize(n, -1); low.resize(n, -1); used.resize(n, false); } void dfs(int u, int prev) { used[u] = true; ord[u] = k ++; low[u] = ord[u]; int cnt = 0; for (auto v : g[u]) if (v != prev) { if (ord[v] < ord[u]) { tmp.emplace_back(min(u, v), max(u, v)); } if (!used[v]) { cnt ++; dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] >= ord[u]) { bc.push_back({}); while (true) { pair<int, int> e = tmp.back(); bc.back().emplace_back(e); tmp.pop_back(); if (min(u, v) == e.first && max(u, v) == e.second) { break; } } } } else { low[u] = min(low[u], ord[v]); } } } };
以下の問題で使えます（この問題では上の実装のような高速なやり方ではなくてもできます）。
https://beta.atcoder.jp/contests/arc062/tasks/arc062_d
以上です。
参考
https://en.wikipedia.org/wiki/Biconnected_component
http://www.prefield.com/algorithm/graph/articulation_point.html
