POJ 3249 Test for Job

举报
Linux猿 发表于 2021/08/05 23:27:15 2021/08/05
【摘要】 题目链接~~> 做题感悟:开始做时没处理好,还是按照深搜的思路写了,果断超时,后来改为记忆化才过。 解题思路:从起点开始深搜,在搜每个点的时候要记录最优解,如果最优解已经存在就直接返回dp [ i ] = w[ i ] + dfs ( j )  ; ( i 与j 相连)  。 代码: #include<stdio.h>#...

题目链接~~>

做题感悟:开始做时没处理好,还是按照深搜的思路写了,果断超时,后来改为记忆化才过。

解题思路:从起点开始深搜,在搜每个点的时候要记录最优解,如果最优解已经存在就直接返回dp [ i ] = w[ i ] + dfs ( j )  ; ( i 与j 相连)  。

代码:


  
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<map>
  4. #include<stack>
  5. #include<string>
  6. #include<string.h>
  7. #include<stdlib.h>
  8. #include<math.h>
  9. #include<vector>
  10. #include<queue>
  11. #include<algorithm>
  12. using namespace std ;
  13. #define pret(a,b) memset(a,b,sizeof(a))
  14. const double PI = 3.1415926 ;
  15. const double esp = 1e-4 ;
  16. const int md= 2810778 ;
  17. const int INF = 99999999 ;
  18. const int MX = 1000005 ;
  19. int n,m,top,ans ;
  20. int w[MX],dp[MX] ;
  21. bool vix[MX] ;
  22. struct node // 统计入度和出度
  23. {
  24. int r,c ;
  25. }T[MX] ;
  26. struct vert // 顶点
  27. {
  28. int head ;
  29. }V[MX] ;
  30. struct Edge
  31. {
  32. int v,next ;
  33. }E[MX] ;
  34. void init() // 初始化
  35. {
  36. pret(dp,0) ;
  37. pret(T,0) ;
  38. pret(w,0) ;
  39. pret(vix,false) ;
  40. pret(V,-1) ;
  41. for(int i=0 ;i<n ;i++)
  42. dp[i]=-INF ;
  43. top=0 ;
  44. ans=-INF ;
  45. }
  46. void add_edge(int u,int v) // 邻接表建图
  47. {
  48. E[top].v=v ;
  49. E[top].next=V[u].head ;
  50. V[u].head=top++ ;
  51. }
  52. int dfs(int x)
  53. {
  54. if(dp[x]!=-INF)
  55. return dp[x] ;
  56. int vx,max=-INF ;
  57. for(int e=V[x].head ; e!=-1 ;e=E[e].next)
  58. {
  59. vx=E[e].v ;
  60. int mx=w[x]+dfs(vx) ;
  61. max= max < mx ? mx : max ;
  62. }
  63. return dp[x]=max ;
  64. }
  65. int main()
  66. {
  67. int x,y ;
  68. while(~scanf("%d%d",&n,&m))
  69. {
  70. init() ;
  71. for(int i=0 ;i<n ;i++) // w[] 存每点的花费
  72. scanf("%d",&w[i]) ;
  73. for(int i=0 ;i<m ;i++)
  74. {
  75. scanf("%d%d",&x,&y) ;
  76. x-- ; y-- ;
  77. add_edge(x,y) ;
  78. T[x].c++ ; // 出度加一
  79. T[y].r++ ; // 入度加一
  80. }
  81. for(int i=0 ;i<n ;i++) // 处理终点
  82. if(!T[i].c)
  83. dp[i]=w[i] ;
  84. for(int i=0 ;i<n ;i++) // 从入读为零的点开始
  85. if(!T[i].r)
  86. {
  87. int mx=dfs(i) ;
  88. ans= ans < mx ? mx : ans ;
  89. }
  90. printf("%d\n",ans) ;
  91. }
  92. return 0 ;
  93. }


 

 

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/23767219

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。