当前位置: 代码迷 >> 综合 >> poj 3249 Test for Job 图上dp(记忆化搜索)
  详细解决方案

poj 3249 Test for Job 图上dp(记忆化搜索)

热度:71   发布时间:2024-01-19 06:13:02.0

题意:

给一个n个点的DAG,每个点有一个值p,现在要在图上找一个入度为0到出度为0的路径,使路径上的点的p值和最大。

分析:

dp[v]记录以点v为起点能获得的最大值,搜一遍即可。

代码:

//poj 3249
//sep9
#include <iostream>
using namespace std;
const int maxN=100024;
const int maxM=1000024;
int n,m,e;
int p[maxN],head[maxN],dp[maxN],vis[maxN];
int in[maxN];
struct Edge
{int v,next;
}edge[maxM];void dfs(int u)
{vis[u]=1;	int i,flag=0;for(i=head[u];i!=-1;i=edge[i].next){flag=1;int v=edge[i].v;if(!vis[v])dfs(v);dp[u]=max(dp[u],p[u]+dp[v]);}if(flag==0)dp[u]=p[u];
}
int main()
{while(scanf("%d%d",&n,&m)==2){int i;for(i=1;i<=n;++i)scanf("%d",&p[i]);e=0;memset(head,-1,sizeof(head));memset(in,0,sizeof(in));while(m--){int a,b;scanf("%d%d",&a,&b);in[b]=1;edge[e].v=b;edge[e].next=head[a];head[a]=e++;}	memset(vis,0,sizeof(vis));	for(i=1;i<=n;++i) dp[i]=INT_MIN;for(i=1;i<=n;++i)if(!vis[i])dfs(i);int ans=INT_MIN;for(i=1;i<=n;++i)if(in[i]==0)ans=max(ans,dp[i]);printf("%d\n",ans);}return 0;	
} 


  相关解决方案