题解：P5008 [yLOI2018] 锦鲤抄

· · 题解

题意

题意简化版说的很清楚了。

分析

我们先贪心的思考，在选点时一定是优先选权值大的。然后我们再考虑哪些点能选。

先把图缩点变成一个 DAG 然后，我们发现所有入度不为 0 的强连通分量的所有点都是可选点，反之则其中必须有一个点作为火源，也就是必须留一个点不选，所以尽量贪权值最小的不选。

看数据范围时，我们发现题目不保证没有自环，还是个善良题面，于是我们思考自环会导致什么。容易发现，如果一个强连通分量中不选的点有自环，则其可以被选。

综上，把满足条件的点挑出来，排个序，取前 k 个，累加然后输出，即可切掉本题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10, K = 20, mod = 1e9 + 7;
int n, m, f[N], dfn[N], ar, a[N], low[N], ins[N], scc[N], col, cnti[N], en[N];
vector <int> edge[N], blg[N];
stack <int> st;
int chkmn(int &a, const int &b) {return a = min(a, b);}
void tarjan(int p)
{
  dfn[p] = low[p] = ++ ar;
  st.push(p); ins[p] = 1;
  for (auto to : edge[p])
  {
    if (!dfn[to])
    {
      tarjan(to);
      chkmn(low[p], low[to]);
    }
    else if (ins[to])
      chkmn(low[p], dfn[to]);
  }
  if (low[p] == dfn[p])
  {
    col ++;
    while (!st.empty())
    {
      int t = st.top(); st.pop();
      ins[t] = 0;
      scc[t] = col;
      blg[col].emplace_back(t);
      if (t == p)
        break;
    }
  }
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int k;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i ++) cin >> a[i];
  while (m --)
  {
    int u, v;
    cin >> u >> v;
    edge[u].push_back(v);
  }
  for (int i = 1; i <= n; i ++) if (!dfn[i]) tarjan(i);
  for (int i = 1; i <= n; i ++){
    for (auto to : edge[i])
    {
      if (scc[to] != scc[i]) cnti[scc[to]] ++;
      if (to == i) en[scc[i]] = 1;
    }
  }
  auto cmp = [](int x, int y){return a[x] > a[y];};
  vector <int> p;
  for (int i = 1; i <= col; i ++)
  {
    if (en[i] || cnti[i]) for (auto it : blg[i]) p.emplace_back(a[it]);
    else
    {
      sort(blg[i].begin(), blg[i].end(), cmp);
      for (int j = 0; j < blg[i].size() - 1; j ++) p.emplace_back(a[blg[i][j]]);
    }
  }
  int ans = 0;
  if (k > p.size()) k = p.size();
  nth_element(p.begin(), p.begin() + k, p.end(), greater<int>());
  for (int i = 0; i < k; i ++)  ans += p[i];//;, cout << p[i] << " ";
  // cout << endl;
  cout << ans << endl;
  return 0;
}