Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://poj.org/problem?id=1949#
题意：#
有n个任务，第i个任务需要时间xi来完成，并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。
给你任务信息，问你最短需要多少时间来完成任务。
思路：#
拓扑排序+dp
拓扑排序的过程中做个dp，可以保证dp的顺序…
对于这道题，找出每条依赖链，然后做dp即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月07日 星期二 13时52分27秒
4File Name :3249.cpp
5************************************************ */
6
7#include <iostream>
8#include <cmath>
9#include <queue>
10#include <cstdio>
11#include <cstring>
12#define PB push_back
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
21
22using namespace std;
23const double eps = 1E-8;
24const int dx4[4]={1,0,0,-1};
25const int dy4[4]={0,-1,1,0};
26const int inf = 0x3f3f3f3f;
27const int N=1E5+7;
28vector <int>edge[N];
29int in[N],out[N];
30int n;
31int dp[N];
32int val[N];
33void init()
34{
35 for ( int i = 0 ; i < N ; i++) edge[i].clear();
36 ms(in,0);
37 ms(out,0);
38 ms(dp,0xca);
39 // cout<<"dp:"<<dp[1]<<endl;
40}
41void topo()
42{
43 queue<int>Q;
44 for ( int i = 1 ; i <= n ; i++)
45 if (in[i]==0) Q.push(i),dp[i] = val[i];
46
47 while (!Q.empty())
48 {
49 int cur = Q.front();
50// cout<<"cur:"<<cur<<endl;
51 Q.pop();
52 int siz = edge[cur].size();
53 for ( int i = 0 ; i < siz ; i++)
54 {
55 int v = edge[cur][i];
56// printf("%d->%d val[v]:%d dp[cur]: %d dp[v]:%d ",cur,v,val[v],dp[cur],dp[v]);
57 dp[v] = max(dp[v],dp[cur]+val[v]);
58// printf("new dp[v]:%d\n",dp[v]);
59 in[v]--;
60 if (in[v]==0) Q.push(v);
61 }
62 }
63}
64void pr()
65{
66 for ( int i = 1 ; i <= n ; i++) printf("%d%c",dp[i],i==n?'\n':' ');
67}
68int main()
69{
70#ifndef ONLINE_JUDGE
71 freopen("./in.txt","r",stdin);
72#endif
73 while (~scanf("%d",&n))
74 {
75 init();
76 for ( int i = 1 ; i <= n ; i++)
77 {
78 int x,m;
79 x = i;
80 scanf("%d %d",&val[i],&m);
81 while (m--)
82 {
83 int y;
84 scanf("%d",&y);
85 // cout<<"x:"<<x<<" y:"<<y<<endl;
86 edge[y].PB(x);
87 out[y]++;
88 in[x]++;
89 }
90 }
91 topo();
92 int ans = -inf;
93// pr();
94 for ( int i = 1 ; i <= n ; i++) if (!out[i]&&dp[i]>ans) ans = dp[i];
95 printf("%d\n",ans);
96 }
97
98
99
100#ifndef ONLINE_JUDGE
101 fclose(stdin);
102#endif
103 return 0;
104 }