JAG 夏合宿 2015 Day2 G: Escape

問題

G: Escape - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder

解法

「入ったら頂点1に戻ることができずに確実に終了する点」を列挙する。逆に、これらの点以外の点は常に行き来できるので、その点数は確実に手に入る。あとは戻れない点に設定されている点数の最大値を取れば良い。

コード

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

vector<vector<int>> g;
vector<int> w;

void dfs(int v, int p, vector<bool> &end) {
  if (g[v].size() > 2) return;
  if (v == 0) return;
  end[v] = true;
  w[v] += w[p];
  w[p] = 0;
  for (int u : g[v])
    if (u != p) dfs(u, v, end);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  w.resize(N);
  for (int i = 0; i < N; ++i) cin >> w[i];

  g.resize(N);
  for (int i = 0; i < M; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  vector<bool> end(N, false);
  for (int i = 1; i < N; ++i) {
    if (g[i].size() == 1) {
      end[i] = true;
      dfs(g[i][0], i, end);
    }
  }

  while (true) {
    bool finished = true;
    for (int i = 1; i < N; ++i) {
      if (end[i]) continue;
      int cnt = 0;
      int parent = -1;
      for (int v : g[i]) {
        if (!end[v]) {
          cnt++;
          parent = v;
        }
      }
      if (cnt > 1) continue;

      finished = false;
      assert(cnt > 0);
      assert(parent >= 0);

      int ma = 0;
      for (int v : g[i])
        if (end[v]) {
          ma = max(ma, w[v]);
          w[v] = 0;
        }
      w[i] += ma;
      end[i] = true;
      if (g[parent].size() <= 2) dfs(parent, i, end);
    }
    if (finished) break;
  }

  ll ans = 0;
  for (int i = 0; i < N; ++i) {
    if (end[i]) continue;
    ans += w[i];
  }

  int ma = 0;
  for (int i = 0; i < N; ++i) {
    if (!end[i]) continue;
    ma = max(ma, w[i]);
  }
  cout << (ma + ans) << endl;
}