题解：CF2044G2 Medium Demon Problem (hard version)

STL_Yu · 2026-11-11 16:08:18 · 题解

题解：CF2044G2 Medium Demon Problem (hard version)

思路

定义使第 i 只蜘蛛剩余礼物数为零所需的交换次数为 val_i。若无论怎样 i 的礼物数都恒大于零，则 val_i=\infty。发现一个小性质，在环上的蜘蛛每次都不会损失礼物，所以其对答案没有影响。显然答案为 \max_{i=1}^{n}val_i+2。考虑如何计算 val_i。我们可以对原图跑拓扑排序，假设有一条点 u 到点 v 的边，则 val_v\gets val_v+val_u。如果当前点的入度为零，则更新答案 ans\gets \max(ans,val_i+2)，因为这个点已经无法被其它点贡献了。

Code

::::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,r[200005],d[200005],val[200005];
vector<int>graph[200005];
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){d[i]=0;val[i]=0;graph[i].clear();}
        for(int i=1;i<=n;i++){
            cin>>r[i];
            d[r[i]]++;
            graph[i].push_back(r[i]);
        }
        queue<int>q;
        int ans=2;
        for(int i=1;i<=n;i++){
            val[i]=1;
            if(d[i]==0){q.push(i);ans=max(ans,val[i]+2);}
        }
        while(!q.empty()){
            int qf=q.front();
            q.pop();
            for(auto it:graph[qf]){
                val[it]+=val[qf];
                d[it]--;
                if(d[it]==0){
                    ans=max(ans,val[it]+2);
                    q.push(it);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

::::

评价

这道题目考察了选手对拓扑排序的理解，中规中矩，想一想还是能想出来的。