IBvl战队的膜你赛-题解-C
一扶苏一
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
```cpp
#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;
}
}
}
```