最开始以为有环 发现没环之后
发现是有负数的
把第三个样例画出来 发现疑似是拓扑序之后要是该点为正肯定 放前面 否则放后面
但是发现好像 有些点为负数的可以通过+变回正的也要放前面
那我们贪心跑一遍即可
void solve(){
int n;cin>>n;
vector<int>a(n+1),b(n+1),deg(n+1),dp(n+1);
vector<int>g[n+1];
for(int i=1;i<=n;i++)cin>>a[i],dp[i]=a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
if(b[i]!=-1)g[i].push_back(b[i]),deg[b[i]]++;
}
priority_queue<int>q;
for(int i=1;i<=n;i++)if(!deg[i])q.push(i);
int ans=0;
vector<int>res(n);
int t=0,h=n-1;
while(q.size()){
auto u=q.top();q.pop();
if(dp[u]>=0)res[t]=u,t++;
else res[h]=u,h--;
for(auto v:g[u]){
deg[v]--;
if(!deg[v])q.push(v);
if(dp[u]>=0)dp[v]+=dp[u];
}
}
for(int i=0;i<n;i++){
int u=res[i];
ans+=a[u];
for(auto v:g[u]){
a[v]+=a[u];
}
}
cout<<ans<<endl;
for(auto i:res)cout<<i<<' ';cout<<endl;
}
标签:int,res,--,CF1388D,auto,dp,deg
From: https://www.cnblogs.com/ycllz/p/17898084.html