poj3249Test for Job（记忆化搜索）

/*
   题意：给一个DAG图，n个节点，每个节点都对应一个值，入度为零的点走到出度为零的点，计算所有可能路径
   经过节点值的和最大！
   
   思路：记忆话搜索：也就是如果我们搜索到某一个节点的时候发现该节点已经存在了值，那么直接返回该节点的值！
         和回溯的思想差不多吧！ 
         
         注意：我们是正向建图，并且记忆话搜索是先将子节点的最优值计算出来，然后在计算父节点的最优值
               所以最终的最优值的结果在 入度为0的节点上！ 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector> 
#define INF -0x3f3f3f3f
#define N 100005
using namespace std;

vector<int>g[N];
int v[N], dp[N], vis[N];
int n, m;

int dfs(int u){
   if(g[u].size()==0)
      return  dp[u]=v[u];
   if(dp[u]!=INF)  return dp[u];//如果u节点已经根据其 子节点 计算过了，直接返回 
   int len=g[u].size();
   for(int i=0; i<len; ++i)//否则从它的子节点值 计算它的值！ 
      dp[u]=max(dp[u], dfs(g[u][i])+v[u]);
   return dp[u];
}

int main(){
   while(scanf("%d%d", &n, &m)!=EOF){
       for(int i=1; i<=n; ++i)
          scanf("%d", &v[i]);
       memset(vis, 0, sizeof(vis));
       for(int i=1; i<=n; ++i)
          dp[i]=INF;
       while(m--){
          int u, v;
          scanf("%d%d", &u, &v);
          g[u].push_back(v); 
          vis[v]=1;
       }
       for(int i=1; i<=n; ++i)
          if(!vis[i])
             dfs(i);
       
       int maxCost=INF;    
       for(int i=1; i<=n; ++i){
          if(!vis[i] && dp[i]>maxCost)
             maxCost=dp[i];
          g[i].clear();
       }
       printf("%d\n", maxCost);
   } 
   return 0;
}