题目链接： http://poj.org/problem?id=3249
题目大意：
给定一个有向无环图（DAG），n个点，m条边（1<=n<=100000, 0<=m<=1000000），有若干个入度为0的点，若干个出度为0的点，每个点有一个权值value，要求选择一条从某个入度为0的点到某个出度为0的点的路径，使得整个路径上点的权值之和最大;
分析：
开始自己思考了很久没有结果，因为觉得图比较复杂，后来推荐给了lin神，我和lin神都有大概的想法，比如要进行分层之类的，再后来我自己觉得可以用记忆化搜索写一下，结果还真ac了，估计数据水了，不然记忆化搜索应该会爆栈的才是。
下面第一个代码是记忆化搜索的代码;
后来我们看解题报告，了解到了一个东西： 拓扑排序。 这是一个非常有用的东西，可以把DAG的点按层次排列出来，进行DP保证不会有后效性（个人理解）
代码1（记忆化搜索）：
poj3249
1 /*3249 Accepted 9956K 1829MS C++ 1645B 2012-04-25 14:21:09*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <vector> 8 using namespace std; 9 10 #define mpair make_pair 11 #define pii pair<int,int> 12 #define MM(a,b) memset(a,b,sizeof(a)); 13 typedef long long lld; 14 typedef unsigned long long u64; 15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;} 16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;} 17 #define maxn 100020 18 #define maxm 1000020 19 20 int n,m,top; 21 struct Edge{ 22 int v; 23 Edge *next; 24 } *adj[maxn], edge[maxm]; 25 void Addedge(int u,int v){ 26 Edge *p= &edge[++top]; 27 p->v= v, p->next= adj[u], adj[u]= p; 28 } 29 30 #define inf -2100000000 31 int in[maxn], out[maxn]; 32 int dp[maxn], val[maxn]; 33 34 void dfs(int u){ 35 if( inf != dp[u] ) return; 36 if( in[u]==0 ){ 37 dp[u]= val[u]; 38 return; 39 } 40 for(Edge *p= adj[u];p;p= p->next){ 41 int v= p->v; 42 dfs( v ); 43 up_max( dp[u], dp[v] + val[u] ); 44 } 45 } 46 int main() 47 { 48 while( scanf("%d%d", &n, &m) !=EOF ){ 49 for(int i=1;i<=n;++i) scanf("%d", val+i); 50 top= 0; 51 MM( adj, 0 ); 52 for(int i=1;i<=n;++i) in[i]= out[i]= 0; 53 while( m-- ){ 54 int u,v; 55 scanf("%d%d", &u, &v); 56 out[u]++, in[v]++; 57 Addedge( v, u ); 58 } 59 60 fill( dp+1, dp+1+n, inf ); 61 int ans= inf; 62 for(int i=1;i<=n;++i){ 63 if( out[i] == 0 ){ 64 dfs( i ); 65 up_max( ans, dp[i] ); 66 } 67 } 68 printf("%d\n", ans); 69 } 70 }
代码2（拓扑排序）：
poj3249
1 /*3249 Accepted 10344K 2141MS C++ 1867B 2012-04-25 17:09:31*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <vector> 8 using namespace std; 9 10 #define mpair make_pair 11 #define pii pair<int,int> 12 #define MM(a,b) memset(a,b,sizeof(a)); 13 typedef long long lld; 14 typedef unsigned long long u64; 15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;} 16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;} 17 #define maxn 100020 18 #define maxm 1000020 19 20 int n,m,top; 21 struct Edge{ 22 int v; 23 Edge *next; 24 } *adj[maxn], edge[maxm]; 25 void Addedge(int u,int v){ 26 Edge *p= &edge[++top]; 27 p->v= v, p->next= adj[u], adj[u]= p; 28 } 29 30 int w[maxn]; 31 int in[maxn], out[maxn]; 32 33 #define inf -2100000000 34 int dp[maxn]; 35 int q[maxn]; 36 void Topsort(){ 37 int i, head= 0, tail= 0; 38 for(i=1;i<=n;++i) if( !in[i] ){ q[tail++]= i, dp[i]= w[i]; } 39 while(head<tail){ 40 int u= q[head++]; 41 for(Edge *p= adj[u];p;p= p->next){ 42 int v= p->v; 43 if( --in[v] == 0 ) 44 q[tail++]= v; 45 } 46 } 47 } 48 49 void solve(){ 50 for(int i=0;i<n;++i){ 51 int u= q[i]; 52 for(Edge *p= adj[u];p;p= p->next){ 53 int v= p->v; 54 up_max( dp[v], dp[u] + w[v] ); 55 } 56 } 57 int ans= inf; 58 for(int i=1;i<=n;++i) 59 if( !out[i] ) 60 up_max( ans, dp[i] ); 61 printf("%d\n", ans); 62 } 63 64 int main() 65 { 66 while( scanf("%d%d", &n, &m ) !=EOF ){ 67 for(int i=1;i<=n;++i) scanf("%d", w+i), in[i]=0, out[i]= 0; 68 top= 0; 69 MM( adj, 0 ); 70 for(int i=1;i<=m;++i){ 71 int u,v; 72 scanf("%d%d", &u, &v ); 73 out[u]++, in[v]++; 74 Addedge( u, v ); 75 } 76 fill( dp+1, dp+1+n, inf ); 77 Topsort(); 78 solve(); 79 } 80 }