http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1717

戳入度(in-degree)為零的點下去DFS再取最大值

#include <stdio.h>  
#include <string.h>  
#include <vector>  
#include <algorithm>  
using namespace std;  

int cost[1001];  
long long dp[1001];  
int in_deg[1001];  
vector<int> G[1001];  
long long dfs(int v)  
{  
 if (dp[v]) {  
 return dp[v];  
 }  
 long long res = 0;  
 for (int i = 0; i < G[v].size(); i++) {  
 res = max(dfs(G[v][i]), res);  
 }  
 return dp[v] = res + cost[v];  
}  
int main()  
{  
 int t, n, k, to;  
 scanf("%d", &t);  
 while (t--) {  
 scanf("%d", &n);  
 memset(dp, 0, sizeof(dp));  
 memset(in_deg, 0, sizeof(in_deg));  
 for (int i = 1; i <= n; i++) {  
 scanf("%d%d", &cost[i], &k);  
 while (k--) {  
 scanf("%d", &to);  
 in_deg[to]++;  
 G[i].push_back(to);  
 }  
 }  
 long long ac = 0;  
 for (int i = 1; i <= n; i++) {  
 if (in_deg[i] == 0) {  
 ac = max(dfs(i), ac);  
 }  
 }  
 printf("%I64d\n", ac);  
 for (int i = 1; i <= n; i++) {  
 G[i].clear();  
 }  
 }  
 return 0;  
}