洛谷 P1113 杂务（拓扑排序，递归）

题目大意：

有一个有向无圈图，每个节点看作一个任务，一个任务需要完成必须先完成父亲节点的任务，每个任务都有耗时。假设现在所有不相关任务都可以并行执行，问最短多少时间可以把所有任务完成。

解题思路：

首先，注意题目中比较坑的点。这里必须是完成所有父亲任务才能完成本个任务，所以某个任务的执行时间是

其中par为i的父亲。

有这个递推后，我们就要知道怎么完成这个递推，很明显我们这里要按照拓扑排序的方法访问所有节点，因为要更新本个节点的话必须更新它所有的父亲节点，这里用kahn算法。它本质上是一个修改的BFS，首先让所有入度为0点进入队列，然后删掉出度的边，这时候让入度为0的点入队列的BFS。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e4+10;
int indeg[MAXN];
int poiwei[MAXN];
int dist[MAXN];
vector<vector<int>> gra(MAXN);
vector<vector<int>> backgra(MAXN);
int main(){
  memset(indeg,0,sizeof(indeg));
  int n;cin>>n;
  queue<int> q;
  for(int i=0;i<n;i++){
    int u,time;cin>>u>>time;u-=1;
    poiwei[u]=time;
    int t;
    while(cin>>t && t){
      t-=1;
      indeg[u]++;
      gra[t].emplace_back(u);
      backgra[u].emplace_back(t);
    }
    if(!indeg[u])q.push(u);
  }
  while(!q.empty()){
    int u=q.front();q.pop();
    dist[u]=poiwei[u];
    for(int i=0;i<(int)backgra[u].size();i++){
      int bnx=backgra[u][i];
      dist[u]=max(dist[u],dist[bnx]+poiwei[u]);
    }
    for(int i=0;i<(int)gra[u].size();i++){
      int nx=gra[u][i];
      indeg[nx]--;
      if(!indeg[nx])q.push(nx);
    }
  }
  int ans=-1;
  for(int i=0;i<n;i++){
    ans=max(ans,dist[i]);
  }
  cout<<ans<<endl;
  return 0;
}