POJ 3249 Test for Job（记忆化搜索）

题意:给定一个有向无环图，每个结点有权值，从入度为零的点作为起点，出度为零的点作为终点，要求出到终点时可能的最大权值（权值可能为负数，不过都不超过int）

思路：记忆化搜索，很多人反向建图来做，不知道有什么好处。我还是正常顺序。事先记录好各点的入度，枚举这些点搜索出的可能最大权值。

这种题目的状态转移方程还是很好分析的dp[i] = v[i] + max(dp[u0],dp[u1],......,dp[un]); u0--un为i连接的结点。此外点过多，用邻接表存储。

 
#include    
#include    
#include    
#include    
#include    
#define MAX 111111   
#define INF 0x7FFFFFFF   
using namespace std;  
  
vector edge[MAX];  
int v[MAX],dp[MAX],deg[MAX];  
int n,m;  
  
void init() {  
    for(int i=0; i<=MAX; i++) {  
        dp[i] = -INF;  
        edge[i].clear();  
    }  
    memset(deg,0,sizeof(deg));  
}  
  
int dfs(int v0) {  
    if(dp[v0] != -INF) return dp[v0];  
    int size = edge[v0].size();  
    if(size == 0) return v[v0];  
    int maxx = -INF;  
    for(int i=0; i