题解：P3651 展翅翱翔之时 (はばたきのとき)

· · 题解

题目显然等价于将一个（内向）基环树森林修改为一个环。

思考一会发现图在变成环前可以看成一堆链。

则问题变成断掉总代价最小的边，使得图变为一些链。

发现如果原图是内向树的话做法显然，只需要对每个点保留边权最大的入边，将其余边断掉。

由于基环树可以通过破坏环上的一条边变成树，因此只需要枚举破坏的是哪条边即可。

这样暴力做的复杂度是 \mathcal O\left(n^2\right) 的，考虑如何在断掉一条边时快速判断剩余结构的答案。

不妨先对每个点只保留边权最大的边，计算代价。

发现断掉的边（设其为 u\to v，边权为 w）只有两种情况：

如果是第一种情况，则断掉这条边后，v 的最大入边发生变化。显然总代价要加上边权 w，同时减去 v 的次大入边边权。

如果是第二种情况，显然这条边已经被断掉了，代价不变。

注意需要特判原图已经只有一个环的情况。

至此，可以在 \mathcal O\left(n\right) 的复杂度内完成本题。

:::success[Code]

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

size_t find_circle(size_t curr, const vector<size_t> &nxt, vector<bool> &visited) {
  while (!visited[curr])
    visited[curr] = true, curr = nxt[curr];
  return curr;
}

vector<size_t> get_circle(size_t start, const vector<size_t> &nxt) {
  vector<size_t> circle;
  size_t curr = start;
  do
    circle.push_back(curr), curr = nxt[curr];
  while (curr != start);
  return circle;
}

void mark_block(size_t curr, const vector<vector<size_t>> &prv, vector<bool> &visited) {
  visited[curr] = true;
  for (size_t p : prv[curr])
    if (!visited[p])
      mark_block(p, prv, visited);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);
  size_t n;
  cin >> n;

  vector<size_t> nxt(n);
  vector<vector<size_t>> prv(n);
  vector<int64_t> cost(n), prv_cost_sum(n);
  vector<pair<int64_t, int64_t>> prv_cost_max(n);

  auto update_maxvalue = [](pair<int64_t, int64_t> &cur, int64_t val) {
    if (val > cur.first)
      cur.second = cur.first, cur.first = val;
    else if (val > cur.second)
      cur.second = val;
  };

  for (size_t i = 0; i < n; ++i)
    cin >> nxt[i] >> cost[i], --nxt[i];
  for (size_t i = 0; i < n; ++i)
    prv[nxt[i]].push_back(i);
  for (size_t i = 0; i < n; ++i)
    for (size_t p : prv[i])
      prv_cost_sum[i] += cost[p], update_maxvalue(prv_cost_max[i], cost[p]);

  int64_t total_cost = 0;
  for (size_t i = 0; i < n; ++i)
    total_cost += cost[i] - prv_cost_max[i].first;

  vector<bool> visited(n, false), in_block(n, false);
  for (size_t i = 0; i < n; ++i) {
    if (visited[i])
      continue;
    size_t circle_start = find_circle(i, nxt, in_block);
    mark_block(circle_start, prv, visited);
    auto circle = get_circle(circle_start, nxt);
    if (circle.size() == n)
      break;
    int64_t best_cut = numeric_limits<int64_t>::max();
    for (size_t u : circle)
      if (cost[u] == prv_cost_max[nxt[u]].first)
        best_cut = min(best_cut, prv_cost_max[nxt[u]].first - prv_cost_max[nxt[u]].second);
      else
        best_cut = 0;
    total_cost += best_cut;
  }
  cout << total_cost << '\n';
  return 0;
}

:::