做题感悟:开始做时没处理好,还是按照深搜的思路写了,果断超时,后来改为记忆化才过。
解题思路:从起点开始深搜,在搜每个点的时候要记录最优解,如果最优解已经存在就直接返回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 ; }