题意
给定一个 $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);
}