codeforces-#660-D

codeforces-#660-D

七月 31, 2020

D. Captain Flint and Treasure

题意

有一个长度为n的数组 n<2e5

每个位置有权值val[i] 和一个to[i]

假如取出它将会获得val[i] ,|val[i]|<1e6

并且它的权值会加到 to[i] (假如to[i]!=-1)下标上的 权值上

比如

val: 1 2 3

to: 2 3 -1

那么取完1号位 ans+=1

并且2号位权重变为 2+1=3

然后取2号位 ans+=3

并且3号位权重变为 3+3=6

最后取3号位 ans+=6

每个位置的权值只能取一次

问最大的ans

题解

将每个点构建成图

发现这是一个森林 每个点最多一个出度 但可以有多个入度

假如先取出叶子结点那么叶子结点的权重会被加到其父节点上

于是贪心考虑从叶子结点开始选择取或不取 (这个点的权值是否为正数)

于是想到用拓扑排序的遍历方式搜索所有结点判断要不要先取出来

然后剩下没有被取过的点 从树的根节点开始拿 用dfs顺序遍历

这样子节点的负权值不会被加到根上 而导致ans变小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
ll val[Max],in[Max],out[Max],sum=0,n;
bool vis[Max];
vector<int>mp[Max],vmp[Max];
vector<int>ans;
/*
*/
void dfs(int now){
    if(!vis[now]){
        ans.push_back(now);
        sum+=val[now];
        vis[now]=1;
    }
    for(auto i:vmp[now])dfs(i);
}

void bfs(){
    queue<int>q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    while(!q.empty()){
        int pos=q.front();q.pop();
        //dfn[pos]=cnt++;
        //cout<<pos<<" ";
        for(auto i:mp[pos]){
            in[i]--;
            if(val[pos]>0){
                val[i]+=val[pos];
                sum+=val[pos];
                ans.push_back(pos);
                vis[pos]=1;
            }
            if(!in[i]&&i)q.push(i);
        }
    }
}

int main() {
    Turnoff;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>val[i];
        //in[i]=0,vis[i]=0,out[i]=0;
    }
    for(int i=1;i<=n;i++){
        int to;cin>>to;
        if(to<0)to=0;
        mp[i].push_back(to);
        vmp[to].push_back(i);
        in[to]++;
        if(to)out[i]++;
    }
    bfs();
    //cout<<sum<<endl;
    for(int i=1;i<=n;i++){
        //cout<<out[i]<<" "<<vis[i]<<endl;
        if(out[i])continue;
        //cout<<"dfs "<<i<<endl;
        dfs(i);
    }
    //cout<<endl;
    cout<<sum<<endl;
    for(auto i:ans)cout<<i<<" ";
    cout<<endl;
}