题目描述

难度分:$1900$

输入$n(1 \leq n \leq 2 \times 10^5)$，$m(0 \leq m \leq 2 \times 10^5)$，$k(1 \leq k \leq 10^{18})$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$表示点权。

然后输入$m$条边，每条边输入$x$，$y$，表示一条从$x$到$y$的有向边。节点编号从$1$开始。

保证图中无自环和重边。

如果图中不存在一条长为$k$的路径（路径有$k$个节点），输出$-1$。

否则输出路径上的最大点权的最小值。

输入样例$1$

6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

输出样例$1$

4

输入样例$2$

6 7 100
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

输出样例$2$

10

输入样例$3$

2 1 5
1 1
1 2

输出样例$3$

-1

输入样例$4$

1 0 1
1000000000

输出样例$4$

1000000000

算法

二分答案+拓扑排序

这里首先需要注意的一点是，题目说的是没有自环，并不是没有环。所以如果图中有环，那一定存在一条长度为$k$的路径（因为可以一直打圈直到经过的节点数达到$k$），如果图中没有环，那就求整个图的“直径”，只要这个直径不小于$k$，说明图中也存在长度为$k$的路径。

然后我们发现一个很明显的提示最大点权的最小值，就可以尝试一下二分答案了。对于一个给定的点权上界$limit$，我们对所有点权不超过$limit$的节点建图，在图上跑拓扑排序，一边按照拓扑序进行动态规划。在二分之前注意特判一下整个图没有边的情况。

动态规划

状态定义

$dp[u]$表示以$u$节点为终点的最长链长度。

状态转移

状态转移方程为$dp[u]=max_vdp[v]+1$，其中$v$是$u$的所有前驱节点。

二分答案

1. 如果在$limit$的限制下，能够从图中找到长度为$k$的路径，就记录答案，并往左搜索看能不能更小。
2. 否则增大$limit$，往右搜索。

复杂度分析

时间复杂度

外面的二分时间复杂度为$O(log_2A)$，$A$是数组$a$的极差。二分的内部会进行拓扑排序，时间复杂度为$O(n+m)$。因此，算法整体的时间复杂度为$O((n+m)log_2A)$。

空间复杂度

DP数组和入度表的空间都是$O(n)$级别；图是用邻接表构建的，空间复杂度为$O(n+m)$。所以空间的瓶颈在于图的邻接表，额外空间复杂度为$O(n+m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, m, a[N];
LL k;

bool check(vector<array<int, 2>>& edges, int limit) {
    unordered_map<int, vector<int>> graph;
    vector<int> in(n + 1), dp(n + 1, 1);
    for(int i = 0; i < m; i++) {
        int x = edges[i][0], y = edges[i][1];
        if(a[x] <= limit && a[y] <= limit) {
            graph[x].push_back(y);
            in[y]++;
        }
    }
    queue<int> q;
    for(int i = 1; i <= n; i++) {
        if(a[i] <= limit && in[i] == 0) {
            q.push(i);
        }
    }
    int maxlen = 1, cnt = 0;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        cnt++;
        for(int nxt: graph[cur]) {
            dp[nxt] = dp[cur] + 1;
            maxlen = max(maxlen, dp[nxt]);
            if(--in[nxt] == 0) {
                q.push(nxt);
            }
        }
    }
    if(maxlen >= k) return true;
    for(int i = 1; i <= n; i++) {
        if(a[i] <= limit) {
            cnt--;
        }
    }
    return cnt < 0;
}

int main() {
    scanf("%d%d%lld", &n, &m, &k);
    int l = 1e9, r = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        l = min(l, a[i]);
        r = max(r, a[i]);
    }
    vector<array<int, 2>> edges;
    for(int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edges.push_back({x, y});
    }
    if(edges.empty()) {
        if(k == 1) {
            printf("%d\n", l);
        }else {
            puts("-1");
        }
        exit(0);
    }
    int ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(edges, mid)) {
            ans = mid;
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}