Japan Alumni Group Summer Camp 2015 Day 2 G - Escape

問題

jag2015summer-day2.contest.atcoder.jp

解法

与えられたグラフを二重辺連結成分分解した際, 例えば頂点数が 2 以上で同じ連結成分になっている場合 (多重辺がないので今回の場合は 3 以上ですが)は, ある連結成分から移ってくる -> その連結成分内の点をたどる -> 最初に通った連結成分に戻る ということが出来ます。
この問題では, このように「1 回ある頂点に訪れてからまた戻ることができるか」というのが重要なファクターの一つになっています。ここらへんを考慮しながら連結成分について木 DP をします。

まず準備として, muri[v] = (ある頂点から頂点 v に移った時, v から元の頂点に戻れるか)という bool 変数を求めておきます(下のソースコードでは cfs() という関数でやってます)。

まず v で表現される連結成分の頂点数が 1 でかつまわりのすべての子頂点 u も muri[u] が true だと v -> (子へ向かう) -> v に戻ってくる といった作戦が通用しないので, v から元の頂点に戻ることが出来ません。

これが準備で, あとは木 DP です。

dfs(v, (p), flag) = (頂点 v にいる時, v に戻るか戻らないかのフラグは flag であるときの, 得られる点数の最大値)
という関数を作ります。flag = 0 のときは v に戻ってくる必要はなく, flag = 1 のときは v に戻ってくる必要があるとします。

まず flag = 1 のときは, v に戻ってこなければならないので, v の子 u について, muri[u] が true になっている場合は, u に向かうことは禁じられます。それ以外のすべての u に対する dfs(u, v, 1) の合計 + v で得られる得点 が dfs(v, 1) の答えです。

また, flag = 0 の時は, まず v に戻れる間になるべく点数を稼いで, その後 v に戻れなくても良いのでどこかの頂点に訪れて 終了, という感じです。

そのために, v の子頂点すべてを u1, u2, ..., um として,
dfs(u1, v, 1) + dfs(u2, v, 1) + ... + dfs(u_(i-1), v, 1) + dfs(u_(i+1), v, 1) + ... + dfs(u_m, v, 1) + dfs(ui, v, 0)
の最大値を 1 <= i <= m について求めれば良いです。

typedef long long Weight;
// 辺を表す構造体
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst) : src(src), dst(dst) {}
    Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void visit(const Graph & g, int v, int u,
        Edges& brdg, vector< vector<int> >& tecomp,
        stack<int>& roots, stack<int>& S, vector<bool>& inS,
        vector<int>& num, int& time) {
    num[v] = ++time;
    S.push(v); inS[v] = true;
    roots.push(v);
    for (auto e : g[v]) {
        int w = e.dst;
        if (num[w] == 0)
            visit(g, w, v, brdg, tecomp, roots, S, inS, num, time);
        else if (u != w && inS[w])
            while (num[roots.top()] > num[w]) roots.pop();
    }
    if (v == roots.top()) {
        brdg.push_back(Edge(u, v));
        tecomp.push_back(vector<int>());
        while (1) {
            int w = S.top(); S.pop(); inS[w] = false;
            tecomp.back().push_back(w);
            if (v == w) break;
        }
        roots.pop();
    }
}

// 無向グラフGを与えた時,それを二重辺連結成分分解する
// brdgが橋のリスト
// tecompが二重辺連結成分のリスト
void bridge(const Graph& g, Edges& brdg, vector< vector<int> >& tecomp) {
    const int n = g.size();
    vector<int> num(n);
    vector<bool> inS(n);
    stack<int> roots, S;
    int time = 0;
    for (int u = 0; u < n; u++) if (num[u] == 0) {
        visit(g, u, n, brdg, tecomp, roots, S, inS, num, time);
        brdg.pop_back();
    }
}

const int MAXN = 100010;
int w[MAXN];
int pos[MAXN];
ll gain[MAXN];
Edges brdg;
vector<vi> tecomp;
bool muri[MAXN];

ll dfs(int v, int p, int flag, const vector<vi>& g) {
    ll ret = 0;
    if (flag == 0) {
        ll sum = 0;
        vector<pll> cand;
        for (int ch : g[v]) {
            if (ch == p) continue;
            pll pp;
            if (muri[ch]) {
                pp.first = dfs(ch, v, 0, g);
                pp.second = 0;
            } else {
                pp.first = dfs(ch, v, 0, g);
                pp.second = dfs(ch, v, 1, g);
                sum += pp.second;
            }
            cand.push_back(pp);
        }
        // second でなるべく稼いでから 0 で突撃
        for (pll pp : cand) {
            ret = max(ret, sum-pp.second + pp.first);
        }
        ret += gain[v];
        return ret;
    } else {
        ret = gain[v];
        for (int ch : g[v]) {
            if (ch == p) continue;
            if (tecomp[ch].size() > 1) {
                ret += dfs(ch, v, 1, g);
            }
        }
        return ret;
    }
}

void cfs(int v, int p, const vector<vi>& g) {
    bool cnt = true;
    for (int ch : g[v]) {
        if (ch == p) continue;
        cfs(ch, v, g);
        if (!muri[ch]) cnt = false;
    }
    if (cnt && tecomp[v].size() == 1) muri[v] = true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < N; i++) cin >> w[i];
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].emplace_back(u, v);
        G[v].emplace_back(v, u);
    }
    bridge(G, brdg, tecomp);
    // 木の作成
    int n = tecomp.size();
    vector<vector<int> > g(n);
    for (int i = 0; i < n; i++) {
        for (int el : tecomp[i]) pos[el] = i;
    }
    for (Edge e : brdg) {
        g[pos[e.src]].push_back(pos[e.dst]);
        g[pos[e.dst]].push_back(pos[e.src]);
    }
    for (int i = 0; i < n; i++) {
        for (int el : tecomp[i]) {
            gain[i] += w[el];
        }
    }
    cfs(pos[0], -1, g);
    cout << dfs(pos[0], -1, 0, g) << endl;
    return 0;
}