D. Toss a Coin to Your Graph_二分+拓扑

题目大意

在图中找一个长度大于等于k的链使得其中的最大值最小。

思路和代码

很好的题目

首先，最大值的最小很容易就可以想到二分

每次在值小于等于mid的图里面做拓扑序bfs，维护ds数组，dsi表示从拓扑序起点到点i的最多点数。

ll n , m , k ; 

int a[N] ;

bool ck(ll x , vct > &eg){
	//用所有数值小于等于x的点建图 
	//找一条长度大于k的链 
	vct ds(n + 1 , 0) ;
	vct din(n + 1 , 0) ;
	vct ing(n + 1 , 0) ;
	int num = 0 ;
	rep(u , 1 , n){
		if(a[u] > x) continue ;
		num ++ ;
		ing[u] = 1 ;
		for(int v : eg[u]){
			if(a[v] > x) continue ;
			din[v] ++ ;
		}
	}
	
	queue q ;
	rep(i , 1 , n)
	if(ing[i] && !din[i]){
		q.push(i) ;
		ds[i] = 1 ;
	}
	while(q.size()){
		int now = q.front() ;
		q.pop() ;
		num -- ;
		for(int nxt : eg[now]){
			if(!ing[nxt]) continue ;
			ds[nxt] = max(ds[nxt] , ds[now] + 1LL) ;
			if(! -- din[nxt]) q.push(nxt) ;
		}
	}

	if(num > 0) return 1 ;
	rep(i , 1 , n)
	if(ing[i] && ds[i] >= k) return 1 ;
	return 0 ;
}

void solve(){
	cin >> n >> m >> k ;
	get1(a , 1 , n) ;
	
	vct > eg(n + 1) ;
	rep(i , 1 , m){
		int u , v ;
		cin >> u >> v ;
		eg[u].pb(v) ;
	}
	
	ll l = 1 , r = mod ;
	while(l < r){
//		cout << l << " " << r << "," ;
		int mid = l + r >> 1 ;
		if(ck(mid , eg)) r = mid ;
		else l = mid + 1 ;
	}
	cout << (l < mod ? l : -1) << "\n" ;
}//code_by_tyrii