1 /* 2    题意：给一个DAG图，n个节点，每个节点都对应一个值，入度为零的点走到出度为零的点，计算所有可能路径 3    经过节点值的和最大！ 4     5    思路：记忆话搜索：也就是如果我们搜索到某一个节点的时候发现该节点已经存在了值，那么直接返回该节点的值！ 6          和回溯的思想差不多吧！  7           8          注意：我们是正向建图，并且记忆话搜索是先将子节点的最优值计算出来，然后在计算父节点的最优值 9                所以最终的最优值的结果在 入度为0的节点上！ 10 */11 #include<iostream>12 #include<cstdio>13 #include<cstring>14 #include<algorithm>15 #include<vector> 16 #define INF -0x3f3f3f3f17 #define N 10000518 using namespace std;19 20 vector<int>g[N];21 int v[N], dp[N], vis[N];22 int n, m;23 24 int dfs(int u){25    if(g[u].size()==0)26       return  dp[u]=v[u];27    if(dp[u]!=INF)  return dp[u];//如果u节点已经根据其 子节点 计算过了，直接返回 28    int len=g[u].size();29    for(int i=0; i<len; ++i)//否则从它的子节点值 计算它的值！ 30       dp[u]=max(dp[u], dfs(g[u][i])+v[u]);31    return dp[u];32 }33 34 int main(){35    while(scanf("%d%d", &n, &m)!=EOF){36        for(int i=1; i<=n; ++i)37           scanf("%d", &v[i]);38        memset(vis, 0, sizeof(vis));39        for(int i=1; i<=n; ++i)40           dp[i]=INF;41        while(m--){42           int u, v;43           scanf("%d%d", &u, &v);44           g[u].push_back(v); 45           vis[v]=1;46        }47        for(int i=1; i<=n; ++i)48           if(!vis[i])49              dfs(i);50        51        int maxCost=INF;    52        for(int i=1; i<=n; ++i){53           if(!vis[i] && dp[i]>maxCost)54              maxCost=dp[i];55           g[i].clear();56        }57        printf("%d\n", maxCost);58    } 59    return 0;60 }