D. Captain Flint and Treasure(拓扑排序+贪心)

当时没写出来,感觉自己还是太菜了,思维没碰上边

仔细读题,题目说b不存在循环,总是以-1结束

这就意味这开始,肯定有很多点不会受其他点的影响

$拓扑排序!!$

$让i到b_i连一条边,意味着如果选了i,那么a_{b_i}会加上a_i$

$拓扑排序,如果当前的a_i大于0肯定让它传递下去,加入到答案序列去$

$如果小于0,就不应该让它传递下去,但入度还是一样减,加入到临时序列去$

$最后正序输出答案序列,逆序输出临时序列.$

$为啥逆序输出临时序列?因为后进临时序列的一定是在图中深度比较深的$

$如果先选这个点,可能对之前的进入临时序列造成影响,所以逆序。$

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
ll b[maxn],a[maxn],n,in[maxn],ans;
vector<int>vec[maxn],res,fu;
queue<int>q;
int main()
{cin >> n;for(int i=1;i<=n;i++)	cin >> a[i];for(int i=1;i<=n;i++){cin >> b[i];if( b[i]!=-1 )	in[ b[i] ]++,vec[i].push_back( b[i] );}for(int i=1;i<=n;i++)	if( in[i]==0 )	q.push(i);while( !q.empty() ){int u=q.front(); q.pop();ans+=a[u];if( a[u]>=0 )	res.push_back(u);else	fu.push_back(u);for(int i=0;i<vec[u].size();i++){int v=vec[u][i];if( a[u]>=0 )	a[v]+=a[u];if( --in[v]==0 )	q.push(v);}}cout << ans << endl;for(int i=0;i<res.size();i++)	cout << res[i] << " ";for(int i=fu.size()-1;i>=0;i--)	cout << fu[i] << " ";
}