【题解】CF1388D

题目链接

解题思路

考虑每一个i,如果a[i]>0,则先取a[i]再取b[i],否则先取b[i]再取a[i]。但是会有一种情况:a[i]原来是负数,然后经过一系列加法之后变成了正数。这种情况应该先用拓扑排序,当指向i号节点的所有点都已经加上了之后再处理i号点。我们将之前所说的先去a[i]再取b[i]和先取b[i]再取a[i]做成一张图,然后从图的入度为0的点开始任意遍历即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long a[200005],b[200005];
int ind[200005];
int head[200005];
int id[200005];
struct e{
    int nxt,to;
}edge[200005];
int tot=0;
void add_edge(int u,int v){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    head[u]=tot;
    id[v]++;
}
queue<int> q;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        if(b[i]!=-1)ind[b[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(!ind[i])q.push(i);
    }
    long long ans=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        if(b[x]==-1)continue;
        if(a[x]>=0)add_edge(x,b[x]),a[b[x]]+=a[x];
        else add_edge(b[x],x);
        ind[b[x]]--;
        if(!ind[b[x]])q.push(b[x]);
    }
    for(int i=1;i<=n;i++){
        ans+=a[i];
    }
    for(int i=1;i<=n;i++){
        if(!id[i])q.push(i);
    }
    int now;
    cout<<ans<<endl;
    while(!q.empty()){
        now=q.front();q.pop();
        cout<<now<<" ";
        for(int i=head[now];i;i=edge[i].nxt){
            int nxtt=edge[i].to;
            id[nxtt]--;
            if(!id[nxtt])q.push(nxtt);
        }
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/675/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者