poj3249 Test for Job ——拓扑+DP

link:http://poj.org/problem?id=3249 在拓扑排序的过程中进行状态转移，dp[i]表示从起点到 i 这个点所得到的的最大值。比如从u点到v点，dp[v]=max(dp[v], dp[u]+a[v])   a[]数组是点的价值，最终的dp[]数组里面的最大值就是所求的。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
#define N 111111
using namespace std;
int WO[N],NI[N],dp[N],TA[N];
vector<int> V[N]; queue<int> QU;
int main(void)
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    int n,m;
    while (~scanf("%d%d",&n,&m))
    {
        int i,j;
        for(i=0;i<n;++i)
        {
            scanf("%d",TA+i); NI[i]=WO[i]=0; V[i].clear();
            dp[i]=-INF;
        }
        while (m--)
        {
            int u,v;
            scanf("%d%d",&u,&v); u--,v--;
            NI[v]++,WO[u]++; V[u].push_back(v);
        }
        for(i=0;i<n;++i) if(!NI[i]) QU.push(i),dp[i]=TA[i];
        while(!QU.empty())
        {
            int tmp=QU.front(); QU.pop();
            for(i=0;i<V[tmp].size();++i)
            {
                dp[V[tmp][i]]=max(dp[V[tmp][i]],dp[tmp]+TA[V[tmp][i]]);
                if(--NI[V[tmp][i]]==0) QU.push(V[tmp][i]);
            }
        }
        int ans=-INF;
        for(i=0;i<n;++i) if(!WO[i]) ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}

最近变懒了，博客都懒得写了，其实也没什么可写的，o(╯□╰)o