[JOISC 2016] 电报 / Telegraph

题目要求将一颗基环树森林断开一些边并重新连接，使得图形成一个长为

n

的环。

我们可以把问题看成将图拆成若干条链，再重新拼接起来。观察哪些边是必须拆掉的：

入度大于 $1$ 的点，必须将入边拆成只剩一条；
环上必须拆掉至少一条边。

对于不在环上的点，只满足第一种情况，直接保留所有入边中代价最大的，把其他的都拆掉。

而对于在环上的那些，两种情况会有交集，处理起来会麻烦些。考虑通过 DP 处理有没有选择过环上边。每次决策若想保留环上边则会删掉所有其他入边，否则的话保留其他入边中代价最大的那个，别的全部删除。若一条环上边都没删除过，还需要额外删除环上代价最小的边。

特判掉答案本来就合法不用做的情况。

CPP

#include <bits/stdc++.h>
using namespace std;
istream& fin = cin;
ostream& fout = cout;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
auto main(void) -> int {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  size_t n;
  fin >> n;
  vector<pair<size_t, ui>> fa(n);
  vector<vector<pair<size_t, ui>>> mp(n);
  for (size_t i = 0; i < n; ++i) {
    fin >> fa[i].first >> fa[i].second;
    mp[--fa[i].first].emplace_back(i, fa[i].second);
  }
  {
    vector<bool> vis(n);
    size_t p = 0;
    for (; !vis[p]; p = fa[p].first)
      vis[p] = true;
    if (!ranges::count(vis, 0) && p == 0) {
      fout << "0";
      return 0;
    }
  }
  vector<bool> rv(n, true);
  {
    auto deg =
        mp | ranges::views::transform([](auto const& x) { return x.size(); }) |
        ranges::to<vector>();
    queue<size_t> q;
    for (size_t i = 0; i < n; ++i)
      if (deg[i] == 0)
        q.emplace(i);
    while (!q.empty()) {
      size_t p = q.front();
      q.pop();
      rv[p] = false;
      if (--deg[fa[p].first] == 0)
        q.emplace(fa[p].first);
    }
  }
  uli ans = 0;
  for (size_t i = 0; i < n; ++i)
    if (!rv[i]) {
      auto vw = mp[i] | ranges::views::transform(&pair<size_t, ui>::second);
      if (!ranges::empty(vw))
        ans += ranges::fold_left(vw, 0ull, plus()) - ranges::max(vw);
    }
  vector<bool> vis(n);
  for (size_t i = 0; i < n; ++i)
    if (rv[i] && !vis[i]) {
      pair<uli, uli> f{0, numeric_limits<uli>::max() / 2};
      auto minx = numeric_limits<ui>::max();
      for (size_t p = i; !vis[p]; p = fa[p].first) {
        auto it =
            ranges::find_if(mp[p], [&](auto const& v) { return rv[v.first]; });
        auto x = it->second;
        minx = min(minx, x);
        auto vw =
            mp[p] |
            ranges::views::filter([&](auto const& v) { return !rv[v.first]; }) |
            ranges::views::transform(&pair<size_t, ui>::second);
        if (!ranges::empty(vw)) {
          auto y = ranges::fold_left(vw, 0ull, plus());
          auto z = ranges::max(vw);
          f = {f.first + li(y),
               min({f.first + x + y - z, f.second + y, f.second + x + y - z})};
        }
        vis[p] = true;
      }
      ans += min({f.first + minx, f.second});
    }
  fout << ans;
  return 0;
}

[JOISC 2016] 电报 / Telegraph

文章操作

相关推荐

评论

[JOISC 2016] 电报 / Telegraph