[TIOJ] 1717. 專案時程

題目連結:http://tioj.infor.org/problems/1717

---

本題要求對於每個專案的最大值，所以想想就直接DFS就好，而且顯然不能同一個點走太多次，所以要DP，而因為我覺得存原本的圖不好判斷誰是起點，所以不妨存個反過來的圖，甚至開一個假點當作起點，反正答案都會對。大概就這樣吧

#include <bits/stdc++.h>
using namespace std;

#define N 1000

int Time[N+5];
int val[N+5];
bitset<N+5>walked;
vector<int> graph[N+5];
inline void init(int);
int DFS(int);

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		init(n);
		for(int i=1;i<=n;i++){
			int v,sz;
			scanf("%d%d",&v,&sz);
			Time[i]=v;
			if(sz==0) graph[0].push_back(i);
			for(int j=0;j<sz;j++){
				int w;
				scanf("%d",&w);
				graph[w].push_back(i);
			}
		}
		int ans=DFS(0);
		printf("%d\n",ans);
	}
	return 0;
}

int DFS(int w){
	if(walked[w]) return val[w];
	int mm=0;
	val[w] = Time[w];
	for(auto i:graph[w]){
		int sub = DFS(i);
		mm=max(sub,mm);
	}
	val[w]+=mm;
	walked[w]=1;
	return val[w];
}

inline void init(int n){
	walked.reset();
	for(int i=0;i<=n;i++) graph[i].clear();
}