笑点解析
2025-02-15 11:08:13
发布于：广东
66阅读
0回复
0点赞
题目：无根的点
TLE代码↓猜猜哪T了
#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
pair <int, int> edge[200005];
vector <int> v[200005];
int in[200005], a[200005], mx[200005];
int t, n, m, k;
bool check(int val){
memset(in, 0, sizeof(in));//清空数组
memset(mx, 0, sizeof(mx));
queue <int> q;
for(int i = 1; i <= n; i++) v[i].clear();
for(int i = 1; i <= m; i++){
if(a[edge[i].first] <= val && a[edge[i].second] <= val){//如果权值小于等于val可以加入
v[edge[i].first].push_back(edge[i].second);
in[edge[i].second]++;
}
}
for(int i = 1; i <= n; i++){
if(!in[i]) q.push(i);
}
int ct = 0;
while(!q.empty()){//拓扑排序
int head = q.front();
q.pop(), ct++;
for(int i:v[head]){
if((mx[i] = max(mx[i], mx[head] + 1)) >= k) return 1;
if(!(--in[i])) q.push(i);
}
}
if(ct != n) return 1;
return 0;
}
void solve(){
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= m; i++){
cin >> edge[i].first >> edge[i].second;
}
if((--k) == 0){
cout << *min_element(a + 1, a + n + 1) << '\n';
return;
}
int l = 0, r = 1e9 + 10;
while(l <= r){//二分
int mid = l + r >> 1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << (l >= 1e9 ? -1 : l) << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t;
while(t--) solve();
return 0;
}
有帮助，赞一个