POJ 3294

————————————————————————————————————

题目大意：有向图，点有点权，要求从入度为0点开始，以出度为0点作为终点，求一条权值最大的有向路径使经过点的点权和最大（可能存在负值）。

————————————————————————————————————

题目思路：拓扑排序 + dp

————————————————————————————————————

题目细节：

1、本题用到了vector ，可作为vector的一例参考、

2、由于没有加 v.clear() ,使得一开始超时了。（谢过某位同学！）

3、本题的dp部分可以用队列来做。
————————————————————————————————————

源代码：

[cpp]
#include<stdio.h>
    #include<stdlib.h>
    #include<vector>
    using namespace std;
    #define MAX 2147483647

    vector<int> v[100010];
    int in[100010];
    int out[100010];
    long long dp[100010];
    int val[100010];
    int vis[100010];

    long long max(long long a, long long b)
    {
        if(a>b) return a;
        else return b;
    }

    int main()
    {
       int n = 0,m = 0;
       int i = 0,j = 0;
       int x = 0,y = 0;
       long long maxn = 0;
       int c = 0,t = 0;

       while(scanf("%d%d",&n,&m)!=EOF)
       {
           for(i = 1;i<=n;i++)
           {
             scanf("%d",&val[i]);
             in[i] = 0;
             out[i] = 0;
             vis[i] = 0;
             dp[i] = -MAX;
             v[i].clear();
           }

           for(i = 0;i<m;i++)
           {
               scanf("%d%d",&x,&y);
               v[x].push_back(y);
               out[x]++;
               in[y]++;
           }

           for(i = 1;i<=n;i++)
             if(in[i] == 0)
               dp[i] = val[i];

           c = 1;
           while(c<n)
           {
              for(i = 1;i<=n;i++)
              {
                 if(!vis[i] && in[i] == 0)
                 {
                     c++;
                     vis[i] = 1;
                     for(j = 0;j<v[i].size();j++)
                     {
                         t = v[i][j]; www.zzzyk.com
                         dp[t] = max(dp[t],dp[i]+val[t]);
                         in[t]--;
                     }
                 }
              }
           }
           maxn = -MAX;
           for(i = 1;i<=n;i++)
           {
               if(out[i] == 0 && dp[i]>maxn)
                  maxn = dp[i];
           }
           printf("%lld\n",maxn);
       }
       return 0;
    }

作者：violet_xrym

补充：移动开发 , Android ,