CF1679D Toss a Coin to Your Graph...

思路：

二分+有向图判环+有向图最长路径。

实现：

 1 #include
 2 using namespace std;
 3 const int INF=0x3f3f3f3f;
 4 
 5 bool dfs(int x,vector<int>&a,vector<int>&color,vectorint>>&g,int maxv){
 6     color[x]=1;
 7     for(int i=0;i){
 8         int to=g[x][i];
 9         if(a[to]>maxv or color[to]==2)continue;
10         if(color[to]==1){
11             return true;
12         }
13         if(dfs(to,a,color,g,maxv))return true;
14     }
15     color[x]=2;
16     return false;
17 }
18 bool has_cycle(vector<int>&a,vectorint>>&g,int maxv){
19     int n=a.size();
20     vector<int>color(n+1,0);
21     return dfs(0,a,color,g,maxv);
22 }
23 int dfs2(int x,int maxv,vector<int>&a,vector<int>&dp,vectorint>>&g){
24     if(dp[x]!=-1)return dp[x];
25     int maxn=0;
26     for(int i=0;i){
27         int to=g[x][i];
28         if(a[to]>maxv)continue;
29         maxn=max(maxn,dfs2(to,maxv,a,dp,g));
30     }
31     return dp[x]=maxn+1;
32 }
33 int max_len(int maxv,vector<int>&a,vectorint>>&g){
34     int n=a.size();
35     vector<int>dp(n+1,-1);
36     dfs2(0,maxv,a,dp,g);
37     return *max_element(dp.begin()+1,dp.end());
38 }
39 bool check(int maxv,long long k,vector<int>&a,vectorint>>&g){
40     if(has_cycle(a,g,maxv))return true;
41     int maxl=max_len(maxv,a,g);
42     return maxl>=k;
43 }
44 
45 int main(){
46     ios::sync_with_stdio(false);
47     cin.tie(0);
48     int n,m;long long k;
49     while(cin>>n>>m>>k){
50         vector<int>a(n+1,0);
51         for(int i=1;i<=n;i++){
52             cin>>a[i];
53         }
54         vectorint>>g(n+1,vector<int>());
55         for(int i=0;i){
56             int x,y;cin>>x>>y;
57             g[x].push_back(y);
58         }
59         a[0]=INF;
60         for(int i=1;i<=n;i++){
61             g[0].push_back(i);
62         }
63         int maxn=*max_element(a.begin()+1,a.end());
64         int l=0,r=maxn,res=INF;
65         while(l<=r){
66             int m=l+r>>1;
67             if(check(m,k,a,g)){
68                 res=m;r=m-1;
69             }
70             else{
71                 l=m+1;
72             }
73         }
74         if(res==INF)cout<<-1<<endl;
75         else cout<endl;
76     }
77     return 0;
78 }