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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。