题意

给定一个 $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，可以过。

代码

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);
}