AtCoder ARC 098 F - Donation (赤色, 1000 点)

本番中に解きたかった...

• ARC 098 F Donation

問題概要

N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。

初めに、W 円を持った状態で好きな頂点に立つ。 ただし、立つ頂点を s としたとき、As≤W でなくてはならない

その後、以下の 2 種類の操作を好きな順序で好きなだけ繰り返す。

• 今いる頂点と直接辺で結ばれている頂点の中から一つ好きなものを選んで移動する。ただし、移動する際の所持金は Av 円以上でなくてはならない。
• 今いる頂点を v としたとき、Bv 円を頂点 v に寄付する。このとき、所持金が 0 円未満になってはならない。

このゲームは、すべての頂点に 1 度ずつ寄付をするとクリアになります。 このゲームのクリアが可能となる、最小の初期の所持金 W を求めてください。

制約

• 1 <= N, M <= 10⁵
• 1 <= Ai, Bi <= 10⁹

解法

自分はまず「完全グラフだったら...」というのを考えた。その場合、

• Ai - Bi が大きい順に訪問するのがいい

というのがわかる。その解析方法は、よくある「隣り合う同士を swap してよくなる条件を考える」というので導くことができた (僕自身は「操作を逆順にして考える」ということは考えずに上記の結論を導いたが、操作を逆順にするととても自然であった)。

次に一般のグラフだったらどうなるかを考える。基本的には「今残っている頂点から Ai - Bi が大きいものから優先的に寄付するのがよい」ことには変わりない。ただし、その頂点がグラフの関節点になっているとき、その頂点を何度も通過することになるので、先にその頂点に寄付してしまうのは損である。その頂点を最後に通過するときに寄付するのがよい。

具体的には、その頂点 v を取り除いた時に生じる連結成分を C1, C2, ..., CK としたとき、C のうちの最後に行くところを Ck とすると

---

1. Ck 以外の連結成分に一通り寄付して (この過程で v を何度も通過しても構わない)
2. v に寄付して
3. Ck 全体に寄付する

---

という流れにするのがよい。最小値は、C_k に必要な所持金を P とすると、

• (C_k 以外の頂点の B の総和) + max(Av - Bv, P)

になる。このときどの C_k を最後にするのがよいかについては全探索する。

本番ではここまでは考察できていたのに、ここから計算量を落とせなかった。以上の流れを愚直に実装しようと思うと、「グラフの分割」を扱う必要があって計算量が大きくなってしまう。そこで逆順に DP するとよい。あたかも後ろからトップダウン的にメモ化再帰するのを、前からボトムアップでループを回して DP するのに書き換えるような感じである。Union-Find 木を用いて実現できる。やっている処理は Kruskal 法にかなり近い。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
using namespace std;

struct UnionFind {
  vector<int> par;
  vector<int> sz;
    
  UnionFind(int n = 210000) { init(n); }
  void init(int n = 210000) {
    par.resize(n); sz.resize(n);
    for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1;
  }
    
  int root(int x) {
    if (par[x] == x) return x;
    else return par[x] = root(par[x]);
  }
    
  bool issame(int x, int y) {
    return root(x) == root(y);
  }

  int size(int x) {
    return sz[root(x)];
  }

  bool direct(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    par[x] = y;
    return true;
  }
};

int N, M;
vector<long long> a, b;
vector<vector<int> > G;

bool cmp(int i, int j) {
  return a[i] - b[i] < a[j] - b[j];
}

int main() {
  cin >> N >> M;
  a.resize(N); b.resize(N);
  for (int i = 0; i < N; ++i) {
    cin >> a[i] >> b[i];
  }
  G.clear(); 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<int> ord(N);;
  std::iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), cmp);

  vector<long long> sumB(N), dp(N), seen(N, 0);
  for (int i = 0; i < N; ++i) {
    sumB[i] = b[i];
    dp[i] = max(a[i], b[i]);
  }
  UnionFind uf(N);
  for (auto v : ord) {
    set<int> adj;
    for (auto to : G[v]) {
      if (!seen[to]) continue;
      adj.insert(uf.root(to));
    }
    long long tmpsum = b[v];
    for (auto r : adj) {
      tmpsum += sumB[r];
      uf.direct(r, v);
    }
    sumB[v] = tmpsum;
    if (!adj.empty()) {
      long long minv = 1LL<<59;
      for (auto r : adj) {
        long long subB = tmpsum - sumB[r];
        long long tmp = subB + max(a[v] - b[v], dp[r]);
        minv = min(minv, tmp);
      }
      dp[v] = minv;
    }
    seen[v] = true;
  }
  cout << dp[uf.root(0)] << endl;
}