首页 > 代码库 > poj3249 Test for job 【图的DAG dp】
poj3249 Test for job 【图的DAG dp】
#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <stack> #include <vector> using namespace std; const int MAX=111111; int N,E; int v[MAX]; const int MINF=-210000000; int in[MAX],out[MAX]; int dp[MAX]; vector<int>g[MAX]; void tuopu() { stack<int>s; for(int i=1;i<=N;i++) { if(in[i]==0) s.push(i); } int tmp=N; while(tmp--) { int now=s.top();s.pop(); for(int i=0;i<g[now].size();i++) { dp[g[now][i]]=max(dp[g[now][i]],dp[now]+v[g[now][i]]); in[g[now][i]]--; if(!in[g[now][i]]) s.push(g[now][i]); } } } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif while(scanf("%d%d",&N,&E)!=EOF) { for(int i=1;i<=N;i++) { scanf("%d",&v[i]); } for(int i=1;i<=E;i++) { int x,y; scanf("%d%d",&x,&y); out[x]++; in[y]++; g[x].push_back(y); } for(int i=1;i<=N;i++) { if(in[i]==0) dp[i]=v[i]; else dp[i]=MINF; } tuopu(); int maxn=MINF; for(int i=1;i<=N;i++) { if(out[i]==0) maxn=max(maxn,dp[i]); } printf("%d\n",maxn); for(int i=1;i<=N;i++) { g[i].clear(); } memset(v,0,sizeof(int)*N); memset(in,0,sizeof(int)*N); memset(out,0,sizeof(int)*N); memset(dp,0,sizeof(int)*N); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。