题解：P12457 [JOI2025 预选赛 R2] 台球

Clare613 · 2025-05-10 22:42:19 · 题解

临晚再写一篇。

思路

很明显，这是一道拓扑排序题，这里大家可能不知道拓扑排序，那么到这儿了解一下。\ 那么这道题怎么做呢？我们可以用拓扑排序找到每一个点如果要击落那么需要花费的注意力，找到编号最大的即可。\ 具体来说，就是用队列来存储可以选择的数，然后赋值。值得注意的是，可能有的球永远打不下来，如图：\ \ 所以最开始要赋一个极大值，以免永远打不下来的被打下来了。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
queue<int> q;
int a[200005],f[200005],b[200005];
vector<int> g[200005];
signed main(){
    memset(b,0x3f,sizeof(b));
    int n,w;
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>f[i];
        if(f[i]==-1){
            q.push(i);
            b[i]=a[i];
        }
        else{
            g[f[i]].push_back(i);
        }
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(auto i:g[t]){
            if(f[i]!=-1){
                b[i]=b[t]+a[i];
                f[i]=-1;
                q.push(i);
            }
        }
    }
    for(int i=n;i>=1;i--){
        if(w>=b[i]){
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}