D. Captain Flint and Treasure

660Div2 D. Captain Flint and Treasure
题目链接
我们根据题目给出的元素与元素的关系可以得到，i是接在b[i]后面的（b[i]!=-1时)很明显我们可以了解到的是：
元素与元素之间组成了一条链式结构而且是有向的，我们很容易就想到拓扑排序
那么在这个拓扑序里面我们可以利用贪心的思想如果a[i]为正数且b[i]不为-1那么所链接的b[i]所对应的a[b[i]]就加上a[i],否则就不加,然后我们判断a[i]是否正数如果是正数就沿着拓扑序走如果是负数就反着走这样我们就保证答案是最大的（实现这个很简单我们一边沿着拓扑序走一边判断当前数是否是正数，是就储存到正数集合里面否则就储存到负数集合里面，然后正向输出正数集合，逆向输出负数集合就完事了）

#include<bits/stdc++.h> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #define int long long #define maxn 1050000 #define inf 9999969 #define rep(i,a,b) for(int i=a;i<=b;++i) #define fep(i,a,b) for(int i=b;i>=a;--i) #define scf(x) scanf("%lld",&x); #define prf(x) printf("%lld\n",x); #define deprf(x) printf("[%lld]\n",x); #define mymset(x,y) memset(x,y,sizeof(x)); const int mod=1e9+7; using namespace std; int in[maxn]; int a[maxn],b[maxn]; vector<int> z; vector<int> f; signed main() {int n;scf(n);rep(i,1,n)scf(a[i]);rep(i,1,n){scf(b[i]);if(b[i]!=-1){in[b[i]]++;}}queue<int> q;rep(i,1,n)if(!in[i])q.push(i);while(!q.empty()){int x=q.front();q.pop();ans+=a[x];if(a[x]>=0)z.push_back(x);else f.push_back(x);if(b[x]==-1)continue;if(a[x]>=0)a[b[x]]+=a[x];if(--in[b[x]]==0)q.push(b[x]); }prf(ans);int len=z.size();rep(i,0,len-1)printf("%lld ",z[i]);len=f.size();fep(i,0,len-1)printf("%lld ",f[i]); }

总结

以上是生活随笔为你收集整理的D. Captain Flint and Treasure的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。