PKU 1949 Chores

[問題文]
1949 -- Chores

N個の仕事がある。それぞれにかかる時間と、その仕事より必ず先に終わらせなければならない仕事k個の情報が与えられる。
仕事は並列で行うことができる。N個の仕事を終わらせるのにかかる時間を最小化せよ。

[解法]
トポロジカルソート + dp

任意の仕事xに対して、これより先に終わらせなければならない仕事{Pi|(0 <= i <= k)}があるとする。仕事を節点とし、各Piから、仕事xに有向辺を引く。仕事xに閉路があると仮定すると題意から矛盾が生じるので、どの仕事にも閉路がない。つまりDAGになる。
あとはこなすべき仕事をトポロジカルソートしてdpすれば、O(|E|)で解ける。

(ちなみに、間違った愚直解でもなぜかACがもらえます...ェ)

const int MAX_N = 20000;
int N;
vector<int> E[MAX_N];
vector<int> RevE[MAX_N];
bool used[MAX_N];
vector<int>order;
void dfs(int v){
  used[v] = true;
  rep(i,E[v].size())
    if(!used[E[v][i]]) dfs(E[v][i]);
  order.pb(v);
}
void topological_sort(){
  rep(i,N)
    if(!used[i]) dfs(i);
}
int dp[MAX_N];
int T[MAX_N];
int main(){
  while(scanf("%d",&N) != EOF){
    rep(i,N){
      int cost,c;
      scanf("%d %d",&cost,&c);
      T[i] = cost;
      rep(j,c){
	int must; scanf("%d",&must);
	--must;
	E[must].push_back(i);
	RevE[i].push_back(must);
      }
    }
    topological_sort();
    dp[*(order.rbegin())] = T[*(order.rbegin())];
    for(int i = order.size() - 2; i >= 0; i--){
      int s = order[i];
      rep(i,RevE[s].size()) dp[s] = max(dp[s],dp[RevE[s][i]]);
      dp[s] += T[s];
    }
    int ans = *(max_element(dp,dp + N));
    printf("%d\n",ans);
    
  }
}