Codeforce 1388 D. Captain Flint and Treasure 解析(拓樸排序、Stack)

今天我們來看看CF1388D
題目連結

題目
略，請直接看原題。

前言

為什麼
我
想不到
要
用
Stack

很久沒寫blog了，這段時間比較少寫題目，就算寫了也提不太起勁去把想法寫成文章。
然而在開始寫難度2000的題目以後，感覺多了太多我思考時不會想到的解法，因此決定重新開始寫文章了Orz。

想法

首先我們先觀察到，對於所有$b[i]\neq-1$的$i$，如果$a[i]\ge0$，那麼我們最好是要先選這個$i$，這樣接下來要加上的數字有可能會變大。如果$a[i]<0$，那麼我們最好是先不要動這個數字，等看看會不會有辦法讓$a[i]\ge0$。
因此我們會發現這題應該是要用到拓樸排序，也就是我們每次只處理$a[i]$不可能再被改動的$i$。
我們對於所有$b[i]\neq0$的$i$都連一個$i\rightarrow b[i]$的邊，並記錄每個點的入度，並且每次只看入度為零的點$i$。
如果$a[i]\ge0$，那麼我們可以直接選這個點進行操作，並且處理入度的變化。如果$a[i]<0$，由於目前這個點$i$的$a[i]$值已經不可能再被改動了，所以我們希望這個點會在「會被此點影響的點都已經被選過以後」再被加入到答案中，因此我們先把$a[i]$放進stack裡，並處理入度，直到整個拓樸排序流程結束以後，我們一個一個把stack中的$a[i]$值加入答案中。

程式碼:

const int _n=2e5+10;  
int t,n,a[_n],b[_n],in[_n],val;  
VI ans;  
queue<int> q;  
stack<int> st;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n;rep(i,1,n+1)cin>>a[i];rep(i,1,n+1)cin>>b[i];  
  rep(i,1,n+1)if(b[i]!=-1)in[b[i]]++;  
  rep(i,1,n+1)if(!in[i])q.push(i);  
  while(!q.empty()){  
    int x=q.front();q.pop();  
    if(a[x]>=0){  
      ans.pb(x);  
      val+=a[x];if(b[x]!=-1)a[b[x]]+=a[x];  
    }else st.push(x);  
    if(b[x]!=-1){in[b[x]]--;if(!in[b[x]])q.push(b[x]);}  
  }while(!st.empty()){  
    int x=st.top();st.pop();ans.pb(x);  
    val+=a[x];  
  }  
  cout<<val<<'\n';  
  rep(i,0,n)cout<<ans[i]<<' '; cout<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看(由於其實只需要維護入度即可，因此我沒有真的存一個圖)
Submission