Hoi_koro memo

Editorialと異なる解法をしたら更新するblog

AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 E - Weights on Vertices and Edges

atcoder.jp

問題概要

$ N $頂点$ M $辺のグラフ $ G $があり、頂点と辺には重みが与えられている。このグラフから辺を削除して、次の条件を満たすようにしたい。

条件:「削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。」

削除する必要がある辺は最小で何本か。

制約

  • $1\leq N\leq 10^5$
  • $N-1\leq M\leq 10^5$
  • グラフは連結

解法

辺が0本削除された状態で条件をみたしていない辺があるとする。グラフの他の辺が削除されるかどうかにかかわらず、その辺は絶対に削除しなければならない。辺を削除したことで新たに条件に違反する辺が現れたなら、新たに違反した辺も削除する必要がある。このように考えていくと、条件に違反する辺から次々と削除していき、違反する辺がなくなるまでに削除された本数を答えればよいことになる。

辺を1つ削除するたびにすべての辺について条件をみたすか確認しなければならないように思えるが、重みが大きいほど条件に抵触しやすいため重みの降順に一巡するだけでよい。

従って、重みの降順に辺を見ていき、

  • 見ている辺Aが条件をみたしているのかを判定する
  • みたしているなら辺Aを残し、みたしていないなら辺Aを削除する

をという操作を順次行えば解ける。これは

  • 頂点が属する連結成分内の頂点重みの総和を答える
  • 辺を削除したときに連結成分を分割する

の操作ができるデータ構造があれば可能。

この問題では、ある辺が削除されるときには連結成分内のそれより重い辺がすべて削除されている。そのため「$ N $頂点に$ G $の各頂点の重みを持たせた部分永続Union-Findを用意して、$ M $本の辺を軽い方から順にUniteしたもの」は要求をみたす。永続ではなく、操作をUndoできるUnion-Findでも十分。

解答例

#include <bits/stdc++.h>

using LL = long long;
constexpr LL LINF = 334ll << 53;

namespace Problem {
using namespace std;

struct UnionFind {
  vector<pair<LL, LL>> memo;
  vector<LL> par;
  UnionFind(int n) {
    par = vector<LL>(n, -1);
  }
  LL root(int x) {
    if (par[x] < 0) return x;
    return par[x] = root(par[x]);
  }
  LL reversible_root(int x) {
    if (par[x] < 0) return x;
    return reversible_root(par[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (par[x] < par[y]) swap(x, y);
      par[y] += par[x];
      par[x] = y;
    }
    return;
  }
  void reversible_unite(int x, int y) {
    x = reversible_root(x);
    y = reversible_root(y);
    if (x != y) {
      if (par[x] < par[y]) swap(x, y);
      memo.emplace_back(x, par[x]);
      memo.emplace_back(y, par[y]);
      par[y] += par[x];
      par[x] = y;
    }
    return;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  LL reversible_same(int x, int y) {
    return reversible_root(x) == reversible_root(y);
  }
  LL size(int x) {
    return -par[root(x)];
  }
  LL reversible_size(int x) {
    return -par[reversible_root(x)];
  }
  void revert_all() {
    for (int i = memo.size() - 1; i >= 0; --i) {
      par[memo[i].first] = memo[i].second;
    }
    memo.clear();
  }
  void revert(int i) {
    par[memo[i].first] = memo[i].second;
  }
};

class Solver {
 public:
  int n, m;
  UnionFind uf;
  vector<pair<pair<int, int>, pair<LL, int>>> edges;
  Solver(LL n, LL m) : n(n),
                       m(m),
                       uf(n){};

  void solve() {
    //UFに頂点の重みを持たせる
    for (int i = 0; i < n; ++i) {
      int tmp;
      cin >> tmp;
      uf.par[i] = -tmp;
    }

    for (int i = 0; i < m; ++i) {
      int a, b, y;
      cin >> a >> b >> y;
      --a;
      --b;
      edges.push_back({{a, b}, {y, -1}});
    }
    sort(edges.begin(), edges.end(), [&](auto xx, auto yy) { return xx.second.first < yy.second.first; });

    //軽い辺から連結成分を繋いで、uniteしたらメモする
    for (int i = 0; i < m; ++i) {
      int a = edges[i].first.first;
      int b = edges[i].first.second;
      if (uf.reversible_root(a) != uf.reversible_root(b)) {
        edges[i].second.second = uf.memo.size();
        uf.reversible_unite(a, b);
      }
    }

    //条件に違反する辺を削除して、uniteを巻き戻す
    int ans = 0;
    for (int i = m - 1; i >= 0; --i) {
      if (uf.reversible_size(edges[i].first.first) < edges[i].second.first) {
        ans++;
        if (edges[i].second.second != -1) {
          uf.revert(edges[i].second.second);
          uf.revert(edges[i].second.second + 1);
        }
      }
    }
    cout << ans << endl;
  }
};
}  // namespace Problem

signed main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  long long n = 0, m;
  std::cin >> n >> m;

  Problem::Solver sol(n, m);
  sol.solve();
  return 0;
}

note