poj 3249 Test for Job (拓扑排序+dp)
http://poj.org/problem?id=3249
题意：
给一个DAG,现要从一条入度为0的点到一个出度为0的点，问最大点权和。
思路：
其实比较容易想到搜…不过复杂度会炸？
由于到一个点的最大点权和，需要更新完所有到达它的路线之后才能确定。
容易联想到拓扑排序，我们可以在拓扑排序的同时做dp
dp[v] = max(dp[v],dp[u]+a[v])，初始化对于入度为0的点，dp[i] = val[i].
其实拓扑+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,m;
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 dp[v] = max(dp[v],dp[cur]+val[v]);
57 in[v]--;
58 if (in[v]==0) Q.push(v);
59 }
60 }
61}
62int main()
63{
64 #ifndef ONLINE_JUDGE
65 freopen("./in.txt","r",stdin);
66 #endif
67 while (~scanf("%d %d",&n,&m))
68 {
69 init();
70 for ( int i = 1 ; i <= n ; i++) scanf("%d",&val[i]);
71 while (m--)
72 {
73 int x,y;
74 scanf("%d %d",&x,&y);
75// cout<<"x:"<<x<<" y:"<<y<<endl;
76 edge[x].PB(y);
77 out[x]++;
78 in[y]++;
79 }
80 topo();
81 int ans = -inf;
82 for ( int i = 1 ; i <= n ; i++) if (!out[i]&&dp[i]>ans) ans = dp[i];
83 printf("%d\n",ans);
84 }
85
86
87
88 #ifndef ONLINE_JUDGE
89 fclose(stdin);
90 #endif
91 return 0;
92}