あの激熱展開を繰り広げた会津合宿北大セットの E 問題。
「橋以外を壊した方がいいケースもある」ということに終盤間際で気づいてからの、残り 14 秒で通せたのは感動した!!!!!!!
こたつがめさん・シンヤカトーありがとーーー
コンテストでは、「二重辺連結成分分解 + ツリー DP」でやったものの後に「DP は Low Link を求めるついでに出来る」と言われ、やってみた!!!
問題概要
N 頂点 M 辺の連結な重みつき単純無向グラフが与えられる。1 辺削除することを考える。削除したときのスコアを
- 2 つの連結成分に分かれるときは、それぞれの連結成分に含まれる辺の重みの和の差
- 分かれないときは、残された連結成分に含まれる辺の重みの和
とする。スコアの最小値を求めよ。
考えたこと
あ、二重辺連結成分分解だ、重そう...と思った。最初二重辺連結成分分解だと思ったときは、
- Low-Link で橋を求める
- 橋を求めて連結成分ごとにつぶし
- ツリーにする
- できたツリー上でツリー DP (各部分木について重み和をツリー DP で求める)
という感じだと思って、実際それで書いて大変だった。
その後ツカサたんから「わざわざツリーを再構築しなくても、ツリー DP の部分は Low-Link のついでにできる」と教えてもらった。それを実装してみた。
#include <iostream> #include <vector> #include <algorithm> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using pint = pair<int,int>; using Edge = pair<int, long long>; using Graph = vector<vector<Edge> >; Graph G; long long all = 0; long long res = 1LL<<60; pint res_e = pint(1<<29, 1<<29); struct LowLink { // main results vector<int> aps; // articulation points vector<pair<int,int> > brs; // brideges // intermediate results vector<int> seen, ord, low; // dp vector<long long> val; void dfs_lowlink(const Graph &G, int v, int p = -1) { static int time = 0; seen[v] = true; ord[v] = low[v] = time++; int num_of_child = 0; bool exist = false; // for articulation point for (auto e : G[v]) { int ch = e.first; long long w = e.second; if (seen[ch]) { if (ch != p) low[v] = min(low[v], ord[ch]), val[v] += w; // back edge continue; } dfs_lowlink(G, ch, v); val[v] += w + val[ch]; low[v] = min(low[v], low[ch]); // forward edge of DFS-tree if (ord[v] < low[ch]) { brs.emplace_back(v, ch); long long diff = abs(val[ch] - (all - w - val[ch])); if (chmin(res, diff)) res_e = pint(min(v, ch), max(v, ch)); else if (res == diff) chmin(res_e, pint(min(v, ch), max(v, ch))); } if (ord[v] <= low[ch]) exist = true; ++num_of_child; } if ((p == -1 && num_of_child > 1) || (p != -1 && exist)) aps.emplace_back(v); } void solve(const Graph &G) { int N = (int)G.size(); seen.assign(N, 0); ord.resize(N); low.resize(N); val.assign(N, 0); aps.clear(); brs.clear(); for (int v = 0; v < N; ++v) if (!seen[v]) dfs_lowlink(G, v); } }; int main() { int N, M; cin >> N >> M; G.clear(); G.resize(N); for (int i = 0; i < M; ++i) { int u, v; long long w; cin >> u >> v >> w; --u, --v; G[u].emplace_back(v, w); G[v].emplace_back(u, w); all += w; } for (int v = 0; v < N; ++v) { for (auto e : G[v]) { if (chmin(res, all - e.second)) res_e = pint(min(v, e.first), max(v, e.first)); else if (res == all - e.second) chmin(res_e, pint(min(v, e.first), max(v, e.first))); } } LowLink ll; ll.solve(G); cout << res_e.first+1 << " " << res_e.second+1 << endl; }