[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();
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology