题 目 链 接

还是比较好想的，但是不好调...感觉细节挺多...

分析一下：
最小化最大值，显然考虑二分；

对于二分的mid，考虑如何check？

相当于对于mid，我们要判断是否有>k的路径最大值<mid；
所以我们可以对于<=mid的点建图，然后判断是否有>k的路径；
如果有，则mid满足，r = mid；否则l = mid + 1

如何判断是否有>k的路径？

首先如果有环的话肯定可以；
否则的话找最长的那条链，bfs一下，或topsort一下也行

综合判环，我们直接用topsort就行

注意别用set，太慢了，直接TLE了...

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<cmath> 
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;

#define pb push_back
#define coutt cout<<"------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;

const int maxn = 2e5 + 7;
const int N = 2e5+7;
const int M = 1e6+7;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 3.14159265359;

ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}

int n,m;
ll k;
int w[maxn];
PII edge[maxn];

vector<int> g[maxn];
int din[maxn];
int depth[maxn];
int vis[maxn];

bool check(int mid)
{
    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        din[i] = 0;
        depth[i] = 0;
        vis[maxn] = 0;
    }

//  set<int> st;
    for(int i=1;i<=m;i++)
    {
        int a = edge[i].first;
        int b = edge[i].second;

        if(w[a] <= mid && w[b] <= mid)
        {
//          cout<<a<<' '<<b<<endl;
            g[a].push_back(b);

            vis[a] = vis[b] = 1;
//          st.insert(a);
//          st.insert(b);

            din[b] ++;
        }
    }

    //topsort
    queue<int> q;
//  for(auto i : st)
    int num = 0;
    for(int i=1;i<=n;i++)
        if(vis[i])
        {
            num ++;
            if(din[i] == 0)
            {
                q.push(i);
                depth[i] = 1;
            }
        }

    int cnt = 0;
    while(q.size())
    {
        int u = q.front();
        q.pop();
        cnt++;

        for(auto v : g[u])
        {
            din[v] --;
            depth[v] = max(depth[v],depth[u] + 1);

            if(din[v] == 0) q.push(v);
        }
    }

    if(cnt < num)   return true;//有环

    for(int i=1;i<=n;i++)
        if(vis[i] && depth[i] >= k) return true;
//  for(auto u : st)
//      if(depth[u] >= k) return true;  //能更小

    return false;
}

int main()
{
    scanf("%d %d %lld",&n,&m,&k);

    int l = inf;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        l = min(l,w[i]);
    }

    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        edge[i] = {a,b};
    }

    if(k == 1)
    {
        printf("%d\n",l);
        return 0;
    }

    int r = inf;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    if(r == inf) printf("-1\n");
    else printf("%d\n",r);

    return 0;
}