AOJ 3022 Cluster Network (AUPC 2017 day2-J) (4D)

Block-Cut 木を試すのにすごくいい問題！

• 問題へのリンク

問題概要

頂点数 、辺数 の連結な無向グラフが与えられる（単純とは限らない）。頂点 には、重み がついている。各頂点について、以下の問に答えよ。

【問】
その頂点を除外したグラフを考える。このグラフを構成する各連結成分について、その成分内に含まれる頂点の重みの総和をとる。この総和の最大値を求めよ。

制約

• 

考えたこと

関節点以外の頂点 については、 を除外しても連結成分は 1 個だけであるので、重みの総和から を引いた値が答えである。

関節点について考えよう。まず、もとのグラフを二重頂点連結成分分解して、Block-Cut 木を構築する。そして、各関節点を除去したときの、各連結成分の頂点の重みの総和を求めていけば良い。

全体として、 の計算量で解ける。

コード

#include <bits/stdc++.h>
using namespace std;


// Edge Class
template<class T> struct Edge {
    int from, to;
    T val;
    Edge() : from(-1), to(-1), val(-1) { }
    Edge(int f, int t, T v = -1) : from(f), to(t), val(v) {}
    friend ostream& operator << (ostream& s, const Edge& e) {
        return s << e.from << "->" << e.to;
    }
};

// graph class
template<class T> struct Graph {
    vector<vector<Edge<T>>> list;
    
    Graph() { }
    Graph(int n) : list(n) { }
    Graph(const Graph<T> &G) : list(G.list) { }
    void init(int n) {
        list.assign(n, vector<Edge<T>>());
    }
    Graph &operator = (const Graph &g) {
        list = g.list;
        return *this;
    }

    const vector<Edge<T>> &operator [] (int i) const { return list[i]; }
    const size_t size() const { return list.size(); }
    const void clear() {
        list.clear();
    }
    const void resize(int n) {
        list.resize(n);
    }

    void add_edge(int from, int to, T val = -1) {
        list[from].push_back(Edge(from, to, val));
        list[to].push_back(Edge(to, from, val));
    }

    friend ostream &operator << (ostream &s, const Graph &G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << " -> ";
            for (const auto &e : G[i]) s << e.to << " ";
            s << endl;
        }
        return s;
    }
};

// low-link
template<class T> struct LowLink {
    // results
    vector<int> ord, low;
    vector<int> aps;         // articulation points
    vector<Edge<T>> brs;     // brideges

    // constructor
    LowLink() { }
    LowLink(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // solver
    int dfs(const Graph<T> &G, int t, int v, int p) {
        ord[v] = low[v] = t++;
        int num_of_children = 0;
        bool exist_articulation = false, is_multiple_edge = false;
        for (const auto &e : G[v]) {
            if (ord[e.to] == -1) {
                num_of_children++;
                t = dfs(G, t, e.to, v);
                low[v] = min(low[v], low[e.to]);  // forward edge of DFS-tree
                exist_articulation |= (p != -1) && (low[e.to] >= ord[v]);
                if (ord[v] < low[e.to]) brs.push_back(e);
            } else if (e.to != p || is_multiple_edge) {
                low[v] = min(low[v], ord[e.to]);  // back edge
            } else {
                is_multiple_edge = true;
            }
        }
        if (exist_articulation || (p == -1 && num_of_children > 1)) {
            aps.emplace_back(v);
        }
        return t;
    }

    void solve(const Graph<T> &G) {
        ord.assign(G.size(), -1), low.assign(G.size(), -1);
        for (int v = 0, k = 0; v < (int)G.size(); v++) {
            if (ord[v] == -1) k = dfs(G, k, v, -1);
        }
    }
};

// BiConnected Components decomposition
// block-cut tree (aps: 0, 1, ..., A-1, components: A, A+1, ..., A+C-1)
// (A: size of aps, C: num of components)
template<class T> struct BiConnectedComponentsDecomposition {
    // result
    LowLink<T> ll;
    vector<int> id_ap;   // index of the articulation point (size: V)
    vector<int> id_cc;   // index of the connected component (size: V)
    vector<vector<int>> groups;   // biconnected components (size: C)
    vector<vector<int>> tree;     // block-cut tree (size: A + C)

    // intermediate results
    vector<int> seen, finished;
    vector<vector<pair<int, int>>> grouped_edges;
    vector<pair<int, int>> tmp_edges;

    // constructor
    BiConnectedComponentsDecomposition() { }
    BiConnectedComponentsDecomposition(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // getter, original graph to block-cut tree (v: node of orignal graph)
    int is_ap_original_graph(int v) const {
        return (id_ap[v] != -1);
    }
    int get_id(int v) const {
        return (id_ap[v] == -1 ? id_cc[v] : id_ap[v]);
    }

    // getter, block-cut tree to orignal graph（v: node-id of block-cut tree)
    int is_ap(int v) const {
        return (v < ll.aps.size());
    }
    int get_ap(int v) const {
        if (v >= (int)ll.aps.size()) return -1;  // not ap
        else return ll.aps[v];
    }
    int get_size(int v) const {  // including aps
        if (v < (int)ll.aps.size()) return 1;  // ap
        else return groups[v - ll.aps.size()].size();
    }
    vector<int> get_group(int v) const {
        if (v < (int)ll.aps.size()) return vector<int>({ll.aps[v]});  // ap
        else return groups[v - ll.aps.size()];
    }

    // solver
    void dfs(const Graph<T> &G, int v, int p) {
        seen[v] = true;
        if (G[v].empty()) {
            groups.emplace_back(vector<int>({v}));
        }
        for (const auto &e : G[v]) {
            if (e.to == p) continue;
            if (!seen[e.to] || ll.ord[e.to] < ll.ord[v]) {
                tmp_edges.emplace_back(minmax(v, e.to));
            }
            if (!seen[e.to]) {
                dfs(G, e.to, v);
                if (ll.low[e.to] >= ll.ord[v]) {
                    groups.emplace_back(vector<int>({v}));
                    grouped_edges.emplace_back();
                    int ap = v;
                    while (!tmp_edges.empty()) {
                        const auto &e2 = tmp_edges.back();
                        if (!finished[e2.first] && e2.first != ap) {
                            groups.back().emplace_back(e2.first);
                            finished[e2.first] = true;
                        }
                        if (!finished[e2.second] && e2.second != ap) {
                            groups.back().emplace_back(e2.second);
                            finished[e2.second] = true;
                        }
                        grouped_edges.back().emplace_back(e2);
                        tmp_edges.pop_back();
                        if (e2.first == min(v, e.to) && e2.second == max(v, e.to)) break;
                    }
                }
            }
        }
    }

    void solve(const Graph<T> &G) {
        ll.init(G);
        seen.assign(G.size(), false), finished.assign(G.size(), false);
        for (int v = 0; v < (int)G.size(); v++) {
            if (!seen[v]) dfs(G, v, -1);
        }
        id_ap.assign(G.size(), -1), id_cc.assign(G.size(), -1);
        for (int i = 0; i < (int)ll.aps.size(); i++) {
            id_ap[ll.aps[i]] = i;
        }
        tree.assign(ll.aps.size() + grouped_edges.size(), vector<int>());
        vector<int> last(G.size(), -1);
        for (int i = 0; i < (int)grouped_edges.size(); i++) {
            vector<int> st;
            for (auto [u, v] : grouped_edges[i]) {
                st.push_back(u), st.push_back(v);
            }
            for (auto v : st) {
                if (id_ap[v] == -1) {
                    id_cc[v] = i + ll.aps.size();
                } else if (last[v] != i) {
                    tree[i + ll.aps.size()].push_back(id_ap[v]);
                    tree[id_ap[v]].push_back(i + ll.aps.size());
                    last[v] = i;
                }
            }
        }
    }
};

// AOJ 3022 - Cluster Network
void AOJ_3022() {
    long long N, M, u, v, all = 0;
    cin >> N >> M;
    vector<long long> w(N), res(N, 0);
    for (int i = 0; i < N; i++) cin >> w[i], all += w[i];
    Graph<int> G(N);
    for (int i = 0; i < M; i++) {
        cin >> u >> v, u--, v--;
        G.add_edge(u, v), G.add_edge(v, u);
    }

    // Block-Cut 木上を形成
    BiConnectedComponentsDecomposition<int> bcc(G);

    // 関節点以外について求める
    for (int ov = 0; ov < N; ov++) {
        if (!bcc.is_ap_original_graph(ov)) res[ov] = all - w[ov];
    }

    // 関節点について求める：Block-Cut 木上の DP
    auto tree = bcc.tree;
    vector<long long> sum(tree.size(), 0);
    for (int v = 0; v < tree.size(); v++) {
        const auto &group = bcc.get_group(v);
        for (auto ov : group) sum[v] += w[ov];
    }
    auto rec = [&](auto rec, int v, int p) -> long long {
        const auto &group = bcc.get_group(v);
        long long ma = 0, all_weight = sum[v];
        for (auto ch : tree[v]) {
            if (ch == p) continue;
            long long sub = rec(rec, ch, v);
            if (bcc.is_ap(v)) sub -= sum[v];
            else sub -= sum[ch];
            ma = max(ma, sub), all_weight += sub;
        }

        // 関節点について処理する
        if (bcc.is_ap(v)) {
            int ov = bcc.get_ap(v);
            long long rem = all - all_weight;
            ma = max(ma, rem);
            res[ov] = ma;
        }
        return all_weight;
    };
    rec(rec, 0, -1);

    for (auto val : res) cout << val << endl;
}

int main() {
    AOJ_3022();
}