ACPC 2021 Day2 J を一般グラフで解く (実装編)
Nachia さんの考えたアルゴリズムを実装しました。 www.mathenachia.blog
注意
- 簡単なランダムチェッカーを通しています。
- 時間計算量については確認していませんが、ACPC 2021 Day2 J を AC することはできました。
- 下のコードはグラフが入力された場合に答えるコードです。ACPC 2021 Day2 J を AC できるコードは大部分が同じなので掲載しません。以下のリンクから確認してください。 judge.u-aizu.ac.jp
#include <bits/stdc++.h> using namespace std; struct extended_block_cut_tree{ int N, cnt; vector<vector<int>> G; extended_block_cut_tree(vector<vector<int>> &E){ N = E.size(); vector<int> next(N, -1); vector<int> d(N, -1); vector<int> imos(N, 0); for (int i = 0; i < N; i++){ if (d[i] == -1){ d[i] = 0; dfs1(E, next, d, imos, i); } } cnt = 0; G.resize(N + 1); vector<bool> used(N, false); for (int i = 0; i < N; i++){ if (d[i] == 0){ dfs2(E, d, imos, used, cnt, i); } if (E[i].empty()){ G[i].push_back(N + cnt); G[N + cnt].push_back(i); cnt++; G.push_back({}); } } G.pop_back(); } void dfs1(vector<vector<int>> &E, vector<int> &next, vector<int> &d, vector<int> &imos, int v){ for (int w : E[v]){ if (d[w] == -1){ d[w] = d[v] + 1; next[v] = w; dfs1(E, next, d, imos, w); imos[v] += imos[w]; } else if (d[w] < d[v] - 1){ imos[v]++; imos[next[w]]--; } } } void dfs2(vector<vector<int>> &E, vector<int> &d, vector<int> &imos, vector<bool> &used, int b, int v){ used[v] = true; bool ok = false; for (int w : E[v]){ if (d[w] == d[v] + 1 && !used[w]){ if (imos[w] > 0){ if (!ok){ ok = true; G[v].push_back(N + b); G[N + b].push_back(v); } dfs2(E, d, imos, used, b, w); } else { G[v].push_back(N + cnt); G[N + cnt].push_back(v); cnt++; G.push_back({}); dfs2(E, d, imos, used, cnt - 1, w); } } } if (!ok && d[v] > 0){ G[v].push_back(N + b); G[N + b].push_back(v); } } int size(){ return G.size(); } vector<int> &operator [](int v){ return G[v]; } }; struct ford_fulkerson{ struct edge{ int to, rev, cap; edge(int to, int rev, int cap): to(to), rev(rev), cap(cap){ } }; int N; vector<vector<edge>> G; ford_fulkerson(int N): N(N), G(N){ } void add_edge(int from, int to){ G[from].push_back(edge(to, G[to].size(), 1)); G[to].push_back(edge(from, G[from].size() - 1, 0)); } void max_flow(int s, int t, int F){ int flow = 0; while (flow < F){ vector<int> pv(N, -1); vector<int> pe(N, -1); vector<bool> used(N, false); used[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()){ int v = Q.front(); Q.pop(); int cnt = G[v].size(); for (int i = 0; i < cnt; i++){ int w = G[v][i].to; if (!used[w] && G[v][i].cap > 0){ used[w] = true; pv[w] = v; pe[w] = i; Q.push(w); } } } if (!used[t]){ break; } for (int v = t; v != s; v = pv[v]){ G[pv[v]][pe[v]].cap--; G[v][G[pv[v]][pe[v]].rev].cap++; } flow++; } } }; int main(){ int N, M; cin >> N >> M; vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int u, v; cin >> u >> v; u--; v--; E[u].push_back(v); E[v].push_back(u); } extended_block_cut_tree T(E); int V = T.size(); vector<int> p(V, -1); vector<int> d(V, 0); for (int i = 0; i < V; i++){ if (p[i] == -1){ queue<int> Q; Q.push(i); while (!Q.empty()){ int v = Q.front(); Q.pop(); for (int w : T[v]){ if (w != p[v]){ p[w] = v; d[w] = d[v] + 1; Q.push(w); } } } } } vector<int> bp = {N - 1}; bool ok = false; while (true){ int v = bp.back(); if (v == 0){ ok = true; break; } if (d[v] == 0){ break; } bp.push_back(p[v]); } vector<int> ans(N, 0); if (!ok){ for (int i = 1; i < N - 1; i++){ ans[i] = N - 3; } } else { int L = bp.size(); vector<bool> is_art(N, false); int art_cnt = 0; for (int i = 0; i < L; i++){ if (1 <= bp[i] && bp[i] < N - 1 && T[bp[i]].size() >= 2){ is_art[bp[i]] = true; art_cnt++; } } vector<vector<pair<int, int>>> edge(V - N); for (int i = 0; i < N; i++){ for (int j : E[i]){ if (i < j){ int v; if (d[i] >= d[j]){ v = p[i]; } else { v = p[j]; } edge[v - N].push_back(make_pair(i, j)); } } } vector<int> id(N); for (int i = 1; i < L; i += 2){ int cnt = 0; vector<int> id2; for (int j : T[bp[i]]){ id[j] = cnt; id2.push_back(j); cnt++; } if (cnt == 2){ continue; } vector<vector<int>> E2(cnt); for (pair<int, int> P : edge[bp[i] - N]){ int u = id[P.first]; int v = id[P.second]; E2[u].push_back(v); E2[v].push_back(u); } int s = id[bp[i - 1]]; int t = id[bp[i + 1]]; ford_fulkerson G(cnt * 2); for (int j = 0; j < cnt; j++){ G.add_edge(j, cnt + j); } for (int j = 0; j < cnt; j++){ for (int k : E2[j]){ G.add_edge(cnt + j, k); } } G.max_flow(cnt + s, t, 2); vector<vector<int>> path; for (ford_fulkerson::edge e : G.G[t]){ if (e.cap > 0 && e.to != cnt + t){ vector<int> tmp = {t}; int v = e.to; while (v != cnt + s){ if (v < cnt){ tmp.push_back(v); } for (ford_fulkerson::edge e : G.G[v]){ if (e.cap > 0){ v = e.to; break; } } } tmp.push_back(s); path.push_back(tmp); } } reverse(path[0].begin(), path[0].end()); reverse(path[1].begin(), path[1].end()); for (int j = 0; j < 2; j++){ int cnt1 = path[1].size(); vector<bool> is_path1(cnt, false); for (int k = 1; k < cnt1 - 1; k++){ is_path1[path[1][k]] = true; } vector<vector<int>> E3(cnt); for (int u = 0; u < cnt; u++){ for (int v : E2[u]){ if (!is_path1[u] && !is_path1[v]){ E3[u].push_back(v); } } } extended_block_cut_tree T2(E3); int V2 = T2.size(); vector<int> p2(V2, -1); queue<int> Q2; Q2.push(s); while (!Q2.empty()){ int v = Q2.front(); Q2.pop(); for (int w : T2[v]){ if (w != p2[v]){ p2[w] = v; Q2.push(w); } } } vector<int> path2; path2.push_back(t); for (int v = p2[t]; v != s; v = p2[v]){ if (v < cnt && T2[v].size() >= 2){ path2.push_back(v); } } path2.push_back(s); reverse(path2.begin(), path2.end()); path[0] = path2; int cnt0 = path[0].size(); for (int k = 0; k < cnt0 - 1; k++){ int u = path[0][k]; int v = path[0][k + 1]; bool ee = false; for (int w : E2[u]){ if (w == v){ ee = true; } } if (!ee){ E2[u].push_back(v); E2[v].push_back(u); } } vector<bool> gray(cnt, true); for (int k = 0; k < cnt0; k++){ gray[path[0][k]] = false; } for (int k = 0; k < cnt1; k++){ gray[path[1][k]] = false; } vector<bool> re(cnt, false); vector<bool> used2(cnt, false); for (int k = 0; k < cnt; k++){ if (gray[k] && !used2[k]){ used2[k] = true; bool blue = false; queue<int> Q; Q.push(k); vector<int> cc; while (!Q.empty()){ int v = Q.front(); Q.pop(); cc.push_back(v); for (int w : E2[v]){ if (gray[w] && !used2[w]){ used2[w] = true; Q.push(w); } else if (is_path1[w]){ blue = true; } } } if (!blue){ for (int v : cc){ re[v] = true; } } } } for (int k = 0; k < cnt; k++){ if (re[k]){ E2[k].clear(); } else { vector<int> tmp; for (int v : E2[k]){ if (!re[v]){ tmp.push_back(v); } } E2[k] = tmp; } } swap(path[0], path[1]); } vector<int> type(cnt, -1); for (int v : path[0]){ type[v] = 0; } for (int v : path[1]){ type[v] = 1; } type[s] = 2; type[t] = 2; int cnt0 = path[0].size(); vector<int> pos0(cnt, -1); for (int j = 0; j < cnt0; j++){ pos0[path[0][j]] = j; } int cnt1 = path[1].size(); vector<int> pos1(cnt, -1); for (int j = 0; j < cnt1; j++){ pos1[path[1][j]] = j; } vector<pair<int, int>> E3; vector<bool> used(cnt, false); for (int j = 0; j < cnt; j++){ if (!used[j] && type[j] == -1){ used[j] = true; vector<int> id; vector<int> p0, p1; queue<int> Q; Q.push(j); while (!Q.empty()){ int v = Q.front(); Q.pop(); id.push_back(v); for (int w : E2[v]){ if (!used[w] && type[w] == -1){ used[w] = true; Q.push(w); } else if (type[w] == 0){ p0.push_back(w); } else if (type[w] == 1){ p1.push_back(w); } else if (type[w] == 2){ p0.push_back(w); p1.push_back(w); } } } for (int v : p0){ for (int w : p1){ E3.push_back(make_pair(pos0[v], pos1[w])); } } } } vector<int> mx1(cnt0, cnt1 - 2); vector<int> mn1(cnt0, 1); vector<int> mx2(cnt1, cnt0 - 2); vector<int> mn2(cnt1, 1); for (pair<int, int> P : E3){ int u = P.first; int v = P.second; if (u > 0){ mx1[u - 1] = min(mx1[u - 1], v); } if (u < cnt0 - 1){ mn1[u + 1] = max(mn1[u + 1], v); } if (v > 0){ mx2[v - 1] = min(mx2[v - 1], u); } if (v < cnt1 - 1){ mn2[v + 1] = max(mn2[v + 1], u); } } for (int j = cnt0 - 2; j >= 0; j--){ mx1[j] = min(mx1[j], mx1[j + 1]); } for (int j = 0; j < cnt0 - 1; j++){ mn1[j + 1] = max(mn1[j + 1], mn1[j]); } for (int j = cnt1 - 2; j >= 0; j--){ mx2[j] = min(mx2[j], mx2[j + 1]); } for (int j = 0; j < cnt1 - 1; j++){ mn2[j + 1] = max(mn2[j + 1], mn2[j]); } for (int j = 1; j < cnt0 - 1; j++){ ans[id2[path[0][j]]] += max(0, mx1[j] - mn1[j] + 1); } for (int j = 1; j < cnt1 - 1; j++){ ans[id2[path[1][j]]] += max(0, mx2[j] - mn2[j] + 1); } } for (int i = 1; i < N - 1; i++){ ans[i] += art_cnt; if (is_art[i]){ ans[i] = N - 3; } } } for (int i = 1; i < N - 1; i++){ cout << ans[i]; if (i < N - 2){ cout << ' '; } } cout << endl; }