均衡な辺削除 (Balanced Edge Deletion) [Aizu Competitive Programming Camp 2018 Day 3 E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/E

前提知識

• 二重辺連結成分分解

考察過程

1. 橋である辺と橋でない辺で挙動が分かれるのは見て分かる
2. 橋である辺を削除した場合の連結成分のコストを求めたい
3. 二重辺連結成分分解すれば良さそう
4. 分解後の成分を木として考えれば、dfsして累積和を取って連結成分のコストが求められる
5. 橋でない辺を削除したほうが最適な場合もあるので注意（その削除した辺のコストがあまりにでかい）

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3150016

二重辺連結成分分解を知っているかが重要となる問題になる。
　
二重辺連結成分分解をして、無向グラフを二重辺連結成分を頂点とした木に変換しよう。
その木について部分木のコストをsmとして累積和で求めていけば、
ある辺で切ったときの連結成分のコストの総和は求められる。
すべての辺で切る場合を試して最小コストの辺を求めよう。
　
橋で切らなくても、最小になる場合がある。
橋でない頂点について全体のコスト-辺のコストが最小になる場合もあるので、それも計算すると答え。

int N, M;
int U[101010], V[101010], W[101010];
ll cst[101010];
vector<pair<int,int>> E[101010];
//---------------------------------------------------------------------------------------------------
int dpt[101010]; ll sm[101010];
void dfs(int cu, int _dpt = 1) {
    dpt[cu] = _dpt;
    sm[cu] = cst[cu];
    fore(p, E[cu]) if (!dpt[p.first]) {
        dfs(p.first, _dpt + 1);
        sm[cu] += sm[p.first] + p.second;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> U[i] >> V[i] >> W[i];
    rep(i, 0, M) U[i]--, V[i]--;

    BridgeSCC bs;
    bs.init(N);
    rep(i, 0, M) bs.add_edge(U[i], V[i]);
    bs.scc();

    UnionFind uf(N);
    fore(v, bs.SC) fore(i, v) uf(v.front(), i);

    ll mincst = infl;
    pair<int, int> ans = { U[0], V[0] };
    ll tot = 0;
    rep(m, 0, M) tot += W[m];
    rep(m, 0, M) if(uf[U[m]] == uf[V[m]]) {
        if (tot - W[m] < mincst) {
            mincst = tot - W[m];
            ans = { U[m], V[m] };
        }
        else if (tot - W[m] == mincst) chmin(ans, { U[m], V[m] });
    }

    if (1 < bs.SC.size()) {
        int root = 0;
        rep(m, 0, M) {
            if (uf[U[m]] == uf[V[m]]) cst[uf[U[m]]] += W[m];
            else {
                E[uf[U[m]]].push_back({ uf[V[m]], W[m] });
                E[uf[V[m]]].push_back({ uf[U[m]], W[m] });
                root = uf[U[m]];
            }
        }

        dfs(root);

        rep(m, 0, M) if (uf[U[m]] != uf[V[m]]) {
            int u = uf[U[m]], v = uf[V[m]];
            if (dpt[u] < dpt[v]) swap(u, v);
            ll uc = sm[u];
            ll vc = sm[root] - uc - W[m];

            ll cs = abs(uc - vc);
            if (cs < mincst) {
                mincst = cs;
                ans = { U[m], V[m] };
            }
            else if (cs == mincst) chmin(ans, { U[m], V[m] });
        }
    }

    printf("%d %d\n", ans.first + 1, ans.second + 1);
}