CF 1679 D. Toss a Coin to Your Graph... 二分 + 拓扑 1900

题意：一个有 n 个点，m 条边构成的有向图，每个点有一个值 ai，求出可能的最小的长度为 k 的路径中最大值。

思路：用二分搜索最小的 x，只考虑图中小于等于 x 的点，看能否找到一个环，或者找到一条大于等于 k 的路径。用拓扑排序，找到图中最长的路径并且判断是否有环。

代码：

#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10, P = 1e9 + 7, mod = 998244353;
int n, m;
ll k;
int a[N];
vector<int> g[N];
bool check(int x) {
vector<int> d(n + 1), dp(n + 1);
for(int i = 1; i <= n; i++) {
if(a[i] <= x)
for(auto j : g[i])
d[j]++;
}
queue<int> q;
for(int i = 1; i <= n; i++) {
if(a[i] <= x && !d[i])
q.push(i);
}
int m = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : g[u]) {
if(a[v] <= x) {
dp[v] = max(dp[v], dp[u] + 1);
m = max(m, dp[v]);
d[v]--;
if(!d[v])
q.push(v);
}
}
}
for(int i = 1; i <= n; i++)
if(a[i] <= x && d[i]) return 1;
return m >= k - 1;
}
void solve() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
}
if(k == 1) {
int ans = 1e9;
for(int i = 1; i <= n; i++)
ans = min(ans, a[i]);
cout << ans << endl;
return;
}
int l = 0, r = 1e9 + 1;
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << (l == 1e9 + 1 ? -1 : l) << endl;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tt = 1;
//cin >> tt;
while(tt--) {
solve();
}
return 0;
}

最后

以上就是现实蜗牛最近收集整理的关于CF 1679 D. Toss a Coin to Your Graph... 二分 + 拓扑 1900的全部内容，更多相关CF内容请搜索靠谱客的其他文章。