学步园

思路：DP，仍然是求DAG图上的最长路径，枚举每一个入度为0的点，算出它可以到达的最长路径并且记录最大值即可。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

struct T{
    int u;
    int v;
    int next;
}edge[1000010];

int val[100010] , head[1000010] , in[100010] , dp[100010] , vis[100010];
int n , m , a , b , e;
const int inf = 0x3f3f3f3f;

void init(){
    e = 0;
    memset(in , 0 , sizeof(in));
    memset(head , -1 , sizeof(head));
    memset(dp , 0 , sizeof(dp));
    memset(vis , -1 , sizeof(vis));
}

void addedge(int u , int v){

    edge[e].u = u;
    edge[e].v = v;
    edge[e].next = head[u];
    head[u] = e++;
    return ;
}

int f(int u){
    if(vis[u] != -1) return dp[u];
    int ans = -inf;
    dp[u] = val[u];
    for(int i = head[u] ; i != -1 ; i = edge[i].next){
        ans = max(ans , f(edge[i].v));
    }
    if(ans != -inf) dp[u] += ans;
    vis[u] = 1;
    return dp[u];
}

int main(){

    while(~scanf("%d%d" , &n , &m)){
        init();
        for(int i = 1 ; i <= n ; i ++){
            scanf("%d" , &val[i]);
        }
        for(int i = 1 ; i <= m ; i ++){
            scanf("%d%d" , &a , &b);
            addedge(a , b);
            in[b] ++;
        }
        int ans = -inf;
        for(int i = 1 ; i <= n ; i ++){
            if(!in[i]) ans = max(ans , f(i));
        }
        printf("%d\n" , ans);
    }

    return 0;
}