自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:06:08，当前版本为作者最后更新于2018-11-05 18:13:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[yLOI2018] 锦鲤抄

我永远喜欢银临女神！
这是一篇完全重构后的题解。

Description

给你一张有向图，每个点有一个点权。任意时刻你可以任意选择一个有入度的点，获得它的点权并把它和它的出边从图上删去。最多能选择 $k$ 个点，求最多能获得多少点权。

$1 \leq n \leq 5 \times 10^5 + 4$，$1 \leq m \leq 2 \times 10^6 + 4$，$0 \leq w_i \leq 10^3$，$0 \leq k \leq n$。

Analysis

Algorithm 1

爆搜，搜出所有删点的顺序，复杂度 $O(A_n^k)$，期望得分 $30$ 分。

Algorithm 2

考虑一个 DAG，我们按拓扑序从后向前（若 $u$ 指向 $v$，则 $u$ 在 $v$ 之前）删点，则删除后面的点不会对前面的入度的点产生任何影响。于是按照拓扑序的倒序删点，可以删除所有入度不为 $0$ 的点。只需要把这些点的权值取前 $k$ 大即可。时间复杂度 $O(n + m)$ 或 $O(n \log n + m)$，期望得分 $30$ 分，结合算法 1 可以得到 $60$ 分。

Algorithm 3

子任务 2 明示把一个普通图缩成一个 DAG。对于缩完后的图，同样按照拓扑序的倒叙考虑每个 SCC 的删点方案，则后面的 SCC 不影响前面的 SCC。于是我们只需要考虑一个 SCC 内部的情况。

考虑对于一个 SCC 内的任何一个点 $u$，$u$ 到该 SCC 内其他节点的最短路树构成一棵外向树（或者说，从 $u$ 开始 bfs，只访问该 SCC 内的节点且不重复访问节点，最后会得到一棵 bfs 树，这棵树上所有的边都由父亲指向孩子且在原图上存在）。这棵树具有良好的拓扑结构：只有父亲指向孩子的边，显然是个 DAG。且这棵树上只有 $u$ 一个（在树上）入度为 $0$ 的节点。所以按照算法 2 的考虑，我们可以把除了 $u$ 以外的节点都按照某个顺序删掉。注意这个性质对任何的 $u$ 都成立，也就是说，我们总可以删除某个 SCC 内除了某个点以外的所有点。

• 考虑一个 SCC，如果它在缩点后的图上存在入度，也就是说，有另一个 SCC 内的某点 $s$ 指向该 SCC 内的点 $t$，则我们令 $t$ 为上一段中外向树的根，则删除完该 SCC 内除 $t$ 外的所有节点后，$t$ 仍有入度，可以删除。此时该 SCC 可以被全部删除。
• 如果一个 SCC 在缩点后的图上没有入度，也就是不存在另一个 SCC 内的某点指向该 SCC 内的点，但该 SCC 内存在一个自环，则我们让有自环的点做外向树的根，删除该 SCC 内其余点后，该点仍有入度，可以删除。此时该 SCC 可以被全部删除。
• 如果一个 SCC 在缩点后的图上没有入度，也没有自环，则我们取权值最小的点做外向树的根。此时只有权值最小的点不能被删除。

于是我们把除了上述第三种情况中 SCC 内点权最小的点以外的所有点的点权排序，取前 $k$ 大即可。时间复杂度 $O(m + n \log n)$，期望得分 $100$ 分。

Algorithm 4

取前 $k$ 大无需排序，只需要调用 std::nth_element。它可以把第 $k$ 小的数放在容器第 $k$ 个位置上，且小于第 $k$ 小的数在第 $k$ 个位置左边，大于第 $k$ 小的数在第 $k$ 个数右边（只能保证左右，不能保证比第 $k$ 小的数大/小的数的相对大小顺序）。这一算法的复杂度为 $O(n)$。而缩点的时间复杂度为 $O(n + m)$，所以总复杂度为 $O(n + m)$，期望得分 100 分。实际效率跑的好像还是不如 std::sort 快。

Code

#include <climits>
#include <array>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

const int maxn = 500005;
const int maxm = 2000006;

int n, m, k, vistime, top, scnt, ans;
std::array<int, maxn> w, ind, minw, dfn, low, stk, bel;
std::vector<int> ww;
std::bitset<maxn> slfLoop, instk;
std::array<std::vector<int>, maxn> e;

void dfs(const int u);

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) std::cin >> w[i];
  for (int u, v; m; --m) {
    std::cin >> u >> v;
    e[u].push_back(v);
  }
  for (int i = 1; i <= n; ++i) if (dfn[i] == 0) dfs(i);
  for (int u = 1; u <= n; ++u) {
    for (auto v : e[u]) if (bel[u] != bel[v]) {
      ++ind[bel[v]];
    } else if (u == v) {
      slfLoop.set(bel[u]);
    }
  }
  for (int u = 1; u <= n; ++u) if (ind[bel[u]] || (minw[bel[u]] != u) || slfLoop[bel[u]]) {
    ww.push_back(w[u]);
  }
  while (ww.size() < k) ww.push_back(0);
  std::nth_element(ww.begin(), ww.begin() + k, ww.end(), std::greater<int>());
  for (auto u = ww.begin(), v = ww.begin() + k; u != v; ++u) {
    ans += *u;
  }
  std::cout << ans << std::endl;
  return 0;
}

void dfs(const int u) {
  dfn[u] = low[u] = ++vistime;
  instk[stk[++top] = u] = true;
  for (auto v : e[u]) if (dfn[v] == 0) {
    dfs(v);
    low[u] = std::min(low[u], low[v]);
  } else if (instk[v]) {
    low[u] = std::min(low[u], dfn[v]);
  }
  if (low[u] == dfn[u]) {
    instk[minw[bel[u] = ++scnt] = u] = false;
    for (int v = stk[top--]; v != u; v = stk[top--]) {
      bel[v] = scnt;
      if (w[v] < w[minw[scnt]]) minw[scnt] = v;
      instk[v] = false;
    }
  }
}