POJ 3249 Test for Job（記憶化搜索）

題意:給定一個有向無環圖，每個結點有權值，從入度為零的點作為起點，出度為零的點作為終點，要求出到終點時可能的最大權值（權值可能為負數，不過都不超過int）

思路：記憶化搜索，很多人反向建圖來做，不知道有什麼好處。我還是正常順序。事先記錄好各點的入度，枚舉這些點搜索出的可能最大權值。

這種題目的狀態轉移方程還是很好分析的dp[i] = v[i] + max(dp[u0],dp[u1],......,dp[un]);  u0--un為i連接的結點。此外點過多，用鄰接表存儲。

 
#include <cstdio>   
#include <cstring>   
#include <iostream>   
#include <vector>   
#include <cmath>   
#define MAX 111111   
#define INF 0x7FFFFFFF   
using namespace std;  
  
vector<int> 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<size; i++) {  
        int u = edge[v0][i];  
        maxx = max(maxx,dfs(u));  
    }  
    return dp[v0] = v[v0] + maxx;  
}  
  
int main() {  
    int i,j,a,b;  
    while(scanf("%d%d",&n,&m) != EOF) {  
        init();  
        for(i=1; i<=n; i++) {  
            scanf("%d",&v[i]);  
        }  
        for(i=1; i<=m; i++) {  
            scanf("%d%d",&a,&b);  
            edge[a].push_back(b);  
            deg[b] ++;  
        }  
        int maxx = -INF;  
        for(i=1; i<=n; i++) {  
            if(!deg[i]) {  
                maxx = max(maxx,dfs(i));  
            }  
        }  
        printf("%d\n",maxx);  
    }  
    return 0;  
}