思路：
DAG上DP。一边用kahn模拟拓扑序，一边DP从原点到当前节点最大费用。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<cstring> 5 #include<queue> 6 #include<algorithm> 7 inline int getint() { 8 char ch; 9 while(!isdigit(ch=getchar())); 10 int x=ch^'0'; 11 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 12 return x; 13 } 14 const int N=10001; 15 int len[N],in[N]={0}; 16 std::vector<int> e[N]; 17 int ans=0; 18 void kahn() { 19 std::queue<int> q; 20 bool v[N]; 21 memset(v,0,sizeof v); 22 int f[N]; 23 memset(f,0,sizeof f); 24 q.push(0); 25 v[0]=true; 26 f[0]=0; 27 while(!q.empty()) { 28 int &x=q.front(); 29 ans=std::max(ans,f[x]); 30 for(unsigned i=0;i<e[x].size();i++) { 31 int &y=e[x][i]; 32 f[y]=std::max(f[y],f[x]+len[y]); 33 if(v[y]) continue; 34 if(!--in[y]) { 35 q.push(y); 36 v[y]=true; 37 } 38 } 39 q.pop(); 40 } 41 } 42 int main() { 43 int n=getint(); 44 for(int i=1;i<=n;i++) { 45 getint(); 46 len[i]=getint(); 47 bool isRoot=true; 48 for(int x=getint();x;x=getint()) { 49 in[i]++; 50 e[x].push_back(i); 51 isRoot=false; 52 } 53 if(isRoot) { 54 in[i]=1; 55 e[0].push_back(i); 56 } 57 } 58 kahn(); 59 printf("%d ",ans); 60 return 0; 61 }