AUPC 2018 day3 E: Balanced Edge Deletion
問題
無向グラフが与えられる。ここから辺を一本取り除き、できた連結成分をA, Bとする。(A, Bの片方またはどちらも空かもしれない)
グラフGに対してsum(G) = Σ{w(e)|e∈Gの辺}とする。ただしw(e)は辺eの重みである。
abs(sum(A) - sum(B))を最小化するような取り除くべき辺を求めよ。
複数ある場合は辞書順最小のもの。
制約
グラフの頂点、辺はともに10万以下。
重みは10^9以下の正の整数。
方針
取り除く辺を全部試す。
取り除く辺が橋ならA, Bは二つの成分にわかれる。
そうでない場合は元のグラフをG, 辺をeとして差はsum(G) - w(e)
橋の場合差をひとつひとつ毎回愚直に計算すると遅いが、橋を列挙する際に二重辺連結成分分解をすれば残ったグラフは木になるので、一回だけDFSをすれば各頂点以下の部分木の辺の重みの総和を求めることができて、これを保存しておけば辺一個あたりO(1)で差がわかる。
ソースコード
橋列挙はspaghetti sourceのやつ貼ったので省略。
using ll = long long; int N; vector<vector<tuple<int,int,int,int>>> g; vector<ll> sum; pair<int, int> ansp; ll ans = 1e18, total; void update(int a, int b, ll v){ if(a > b) swap(a, b); pair<int, int> p(a, b); if(ans > v || ans == v && ansp > p){ ans = v; ansp = p; } } long long rec(int c, int p){ ll res = sum[c]; for(auto i: g[c]){ int to, w, ia, ib; tie(to, w, ia, ib) = i; if(to == p) continue; ll s = rec(to, c); res += s + w; update(ia, ib, abs(s - (total - w - s))); } return res; } int main() { cin.tie(0); cin.sync_with_stdio(0); int n, m; cin >> n >> m; vector<tuple<int,int,int>> es; vector<int> to(n); vector<vector<int>> e(n), tecomp; rep(i, m){ int a, b, c; cin >> a >> b >> c; a--; b--; es.emplace_back(a, b, c); e[a].push_back(b); e[b].push_back(a); total += c; } bridge(e, tecomp); rep(i, tecomp.size()) for(int j : tecomp[i]) to[j] = i; sum.resize(N = tecomp.size()); g.resize(N); for(auto i : es){ int ia, ib, c; tie(ia, ib, c) = i; update(ia, ib, total - c); int a = to[ia], b = to[ib]; if(a == b) sum[a] += c; else{ g[a].emplace_back(b, c, ia, ib); g[b].emplace_back(a, c, ia, ib); } } rec(0, 0); cout << ansp.first+1 << " "<< ansp.second+1 << endl; return 0; }