【拓扑排序】

杂务 - 洛谷

模版题。

核心：利用拓扑dp,取前置条件最大值，因为，互不关联的可以同时做，同时做取max

#include<bits/stdc++.h> using namespace std; int n; int t[10010],in[10010],dp[10010],ans; vector<int> g[10010]; void topu(){ 	vector<int> q; 	for(int i = 1;i <= n;i++){ 		if(in[i] == 0){ 			q.push_back(i); 			dp[i] = t[i]; 		} 	 	} 	for(int i = 0;i < q.size();i++){ 		int u = q[i]; 		for(int v:g[u]){ 			dp[v] = max(dp[v],dp[u]+t[v]); 			in[v]--; 			if(in[v] == 0){ 				q.push_back(v); 				dp[v] = max(dp[v],dp[u]+t[v]); 			} 		} 	} } int main() {   	cin>>n;  	for(int i = 1;i <= n;i++){ 		int id; 		cin>>id; 		cin>>t[id]; 		while(1){ 			int x; 			cin>>x; 			if(x == 0)break; 			g[x].push_back(id); 			in[id]++; 		} 	} 	topu(); 	int ans = 0; 	for(int i = 1;i <= n;i++){ 		ans = max(ans,dp[i]); 	} 	cout<<ans;     return 0;   }