[TIOJ] 1717. 專案時程
題目連結:http://tioj.infor.org/problems/1717
本題要求對於每個專案的最大值,所以想想就直接DFS就好,而且顯然不能同一個點走太多次,所以要DP,而因為我覺得存原本的圖不好判斷誰是起點,所以不妨存個反過來的圖,甚至開一個假點當作起點,反正答案都會對。大概就這樣吧
本題要求對於每個專案的最大值,所以想想就直接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();
}
留言
張貼留言