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

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