HDU 3249 Test for job （有向无环图上的最长路，DP）

解题思路：
求有向无环图上的最长路。简单的动态规划
#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cmath>

#define LL long long

using namespace std;

const int MAXN = 100000 + 10;

const int MAXM = 1000000 + 10;

const LL INF = -1 * 20000 * 100000 - 10;

struct Edge

{

    int to, next;

}edge[MAXM];

int tot, head[MAXN];

LL w[MAXN];

LL dp[MAXN];

int out[MAXN], vis[MAXN];

int n, m;

void init()

{

    tot = 0;

    memset(head, -1, sizeof(head));

    memset(w, 0, sizeof(w));

    memset(dp, INF, sizeof(dp));

    memset(vis, 0, sizeof(vis));

    memset(out, 0, sizeof(out));

}

void addedge(int u, int v)

{

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

int dfs(int u)

{

    //cout << u << endl;

    if(vis[u]) return dp[u];

    vis[u] = 1;

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        int v = edge[i].to;

        dp[u] = max(dp[u], (LL)dfs(v));

    }

    if(head[u] == -1) return dp[u] = w[u];

    else return dp[u] = (dp[u] + w[u]);

   // return dp[u];

}

int main()

{

    while(scanf("%d%d", &n, &m)!=EOF)

    {

        init();

        for(int i=1;i<=n;i++) scanf("%d", &w[i]);

        int u, v;

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d", &u, &v);

            addedge(v, u);

            out[u]++;

        }

        LL ans = INF;

        //for(int i=1;i<=n;i++) cout << dp[i] << ' ';

        for(int i=1;i<=n;i++) if(!out[i])ans = max(ans, (LL)dfs(i));

        printf("%d\n", ans);

    }

    return 0;

}