POJ 3249 Test for Job
【摘要】 题目链接~~>
做题感悟:开始做时没处理好,还是按照深搜的思路写了,果断超时,后来改为记忆化才过。
解题思路:从起点开始深搜,在搜每个点的时候要记录最优解,如果最优解已经存在就直接返回dp [ i ] = w[ i ] + dfs ( j ) ; ( i 与j 相连) 。
代码:
#include<stdio.h>#...
做题感悟:开始做时没处理好,还是按照深搜的思路写了,果断超时,后来改为记忆化才过。
解题思路:从起点开始深搜,在搜每个点的时候要记录最优解,如果最优解已经存在就直接返回dp [ i ] = w[ i ] + dfs ( j ) ; ( i 与j 相连) 。
代码:
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<stack>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
#define pret(a,b) memset(a,b,sizeof(a))
-
const double PI = 3.1415926 ;
-
const double esp = 1e-4 ;
-
const int md= 2810778 ;
-
const int INF = 99999999 ;
-
const int MX = 1000005 ;
-
int n,m,top,ans ;
-
int w[MX],dp[MX] ;
-
bool vix[MX] ;
-
struct node // 统计入度和出度
-
{
-
int r,c ;
-
}T[MX] ;
-
struct vert // 顶点
-
{
-
int head ;
-
}V[MX] ;
-
struct Edge
-
{
-
int v,next ;
-
}E[MX] ;
-
void init() // 初始化
-
{
-
pret(dp,0) ;
-
pret(T,0) ;
-
pret(w,0) ;
-
pret(vix,false) ;
-
pret(V,-1) ;
-
for(int i=0 ;i<n ;i++)
-
dp[i]=-INF ;
-
top=0 ;
-
ans=-INF ;
-
}
-
void add_edge(int u,int v) // 邻接表建图
-
{
-
E[top].v=v ;
-
E[top].next=V[u].head ;
-
V[u].head=top++ ;
-
}
-
int dfs(int x)
-
{
-
if(dp[x]!=-INF)
-
return dp[x] ;
-
int vx,max=-INF ;
-
for(int e=V[x].head ; e!=-1 ;e=E[e].next)
-
{
-
vx=E[e].v ;
-
int mx=w[x]+dfs(vx) ;
-
max= max < mx ? mx : max ;
-
}
-
return dp[x]=max ;
-
}
-
int main()
-
{
-
int x,y ;
-
while(~scanf("%d%d",&n,&m))
-
{
-
init() ;
-
for(int i=0 ;i<n ;i++) // w[] 存每点的花费
-
scanf("%d",&w[i]) ;
-
for(int i=0 ;i<m ;i++)
-
{
-
scanf("%d%d",&x,&y) ;
-
x-- ; y-- ;
-
add_edge(x,y) ;
-
T[x].c++ ; // 出度加一
-
T[y].r++ ; // 入度加一
-
}
-
for(int i=0 ;i<n ;i++) // 处理终点
-
if(!T[i].c)
-
dp[i]=w[i] ;
-
for(int i=0 ;i<n ;i++) // 从入读为零的点开始
-
if(!T[i].r)
-
{
-
int mx=dfs(i) ;
-
ans= ans < mx ? mx : ans ;
-
}
-
printf("%d\n",ans) ;
-
}
-
return 0 ;
-
}
-
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/23767219
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)