题解 CF1679D【Toss a Coin to Your Graph...】
Anguei
2022-05-15 21:12:02
## 题意
给定一个 $n$ 个点 $m$ 条边有向图，每个顶点具有点权 $a_i$。保证不含自环（loops）和重边（multi-edges）。
你需要在这张图上找到一个长度为 $k$ （输入指定）的路径，使得路径上所有点权的最大值尽可能小。试求出这个最小值。
若找不到长度为 $k$ 的路径，输出 -1。
$n \leq 2\times 10^5$，$k\leq 10^{18}$。
## 分析
$k$ 的范围这么大，一定不是简单的 `dfs and similar` 题目。
**最大值最小**，想到二分答案。于是需要思考：这道题哪里会有单调性？
不难发现：如果把所有点权超过某个阈值的点都从图上删除，那么图上剩余点的数量和阈值之间就构成了单调关系。阈值越小，被删除的点就会越多，剩余的点就会越少。同时，点的数量与图上最长链的长度也是正相关的——点的数量越多，最长链的长度可能就越长。因此：**二分点权阈值**是此题的关键。
在一定的阈值下，若可以找到长度 $\geq k$ 的一条链，那么阈值可以尝试减小。否则必须增大阈值，以尽量增加最长链长度。
需要注意：如果有环，那么相当于存在一条长度无穷的链……
判环可以使用 dfs 或拓扑排序。求最长链简单 dp 一下就好。
注：其实没有必要真的删除超过阈值的点，在判环、dp 的时候写点特判，跳过不符合要求的点就可以。每次 check 的时候重新建图也可以，常数略大，时限 3s，可以过。
## 代码
```cpp
void solution() {
int n, m;
ll k;
std::cin >> n >> m >> k;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) read(a[i]);
std::vector<std::vector<int>> g(n + 1);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u, v);
g[u].push_back(v);
}
auto hasCycle = [&](const std::vector<std::vector<int>>& g2) {
std::vector<int> ind(n + 1, 0);
for (int i = 1; i <= n; ++i)
for (auto v : g2[i]) ++ind[v];
std::queue<int> q;
for (int i = 1; i <= n; ++i)
if (!ind[i]) q.push(i);
int cnt = 0;
while (!q.empty()) {
++cnt;
int u = q.front();
q.pop();
for (auto v : g2[u]) {
--ind[v];
if (!ind[v]) q.push(v);
}
}
return cnt < n;
};
auto check = [&](int x) {
decltype(g) g2(n + 1);
for (int i = 1; i <= n; ++i) {
if (a[i] > x) continue;
for (auto j : g[i]) {
if (a[j] > x) continue;
g2[i].push_back(j);
}
}
if (hasCycle(g2)) return true;
std::vector<int> dp(n + 1, -1);
auto dfs = [&](auto self, int u) {
if (~dp[u]) return dp[u];
dp[u] = 1;
for (auto v : g2[u]) dp[u] = std::max(dp[u], self(self, v) + 1);
return dp[u];
};
for (int i = 1; i <= n; ++i)
if (dp[i] == -1) dfs(dfs, i);
for (int i = 1; i <= n; ++i)
if (dp[i] >= k) return true;
return false;
};
int l = *std::min_element(a.begin() + 1, a.end());
int r = *std::max_element(a.begin() + 1, a.end());
int mid = (l + r) / 2;
while (l < r) {
if (check(mid))
r = mid;
else
l = mid + 1;
mid = (l + r) / 2;
}
return print(check(mid) ? mid : -1);
}
```