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.2cto.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; 
    }