あの激熱展開を繰り広げた会津合宿北大セットの 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;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2893 均衡な辺削除 (AUPC 2018 day3 E)

問題概要

考えたこと