poj3249 Test for Job ——拓扑+DP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <cctype>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <deque>
10 #include <queue>
11 #include <list>
12 #include <map>
13 #include <set>
14 #include <vector>
15 #include <utility>
16 #include <functional>
17 #include <fstream>
18 #include <iomanip>
19 #include <sstream>
20 #include <numeric>
21 #include <cassert>
22 #include <ctime>
23 #include <iterator>
24 const int INF = 0x3f3f3f3f;
25 const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
26 #define N 111111
27 using namespace std;
28 int WO[N],NI[N],dp[N],TA[N];
29 vector<int> V[N]; queue<int> QU;
30 int main(void)
31 {
32     #ifndef ONLINE_JUDGE
33     freopen("in.txt","r",stdin);
34     #endif // ONLINE_JUDGE
35     int n,m;
36     while (~scanf("%d%d",&n,&m))
37     {
38         int i,j;
39         for(i=0;i<n;++i)
40         {
41             scanf("%d",TA+i); NI[i]=WO[i]=0; V[i].clear();
42             dp[i]=-INF;
43         }
44         while (m--)
45         {
46             int u,v;
47             scanf("%d%d",&u,&v); u--,v--;
48             NI[v]++,WO[u]++; V[u].push_back(v);
49         }
50         for(i=0;i<n;++i) if(!NI[i]) QU.push(i),dp[i]=TA[i];
51         while(!QU.empty())
52         {
53             int tmp=QU.front(); QU.pop();
54             for(i=0;i<V[tmp].size();++i)
55             {
56                 dp[V[tmp][i]]=max(dp[V[tmp][i]],dp[tmp]+TA[V[tmp][i]]);
57                 if(--NI[V[tmp][i]]==0) QU.push(V[tmp][i]);
58             }
59         }
60         int ans=-INF;
61         for(i=0;i<n;++i) if(!WO[i]) ans=max(ans,dp[i]);
62         printf("%d
",ans);
63     }
64     return 0;
65 }