首页 > 代码库 > ZOJ 3527

ZOJ 3527

2024-07-12 13:13:14   220人阅读

这题难在破环。

对于不是环的情况，只需按照一般的树形DP来做，一步一步往根递推就可以了。对于环，则枚举其中一点的两种情况，取或不取，然后再递推，就可以了。当到达某结点的下一结点为环开始的点时，退出即可。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int MAX=210010; 7  8 int fr[MAX],next[MAX],ch[MAX]; 9 int N,qt[MAX],top,in[MAX];10 long long dp[MAX][2],dp1[MAX][2];11 bool flag[MAX];12 13 long long maxt(long long a,long long b){14     if(a>b)return a;15     return b;16 }17 18 long long dfs(int f,int u,long long d[][2], bool choice){19     while(true){20         int v=next[u];21         if(choice) flag[v]=flag[u]=true;22         if(v==f) break;23         d[v][0]+=maxt(d[u][0],d[u][1]);24         d[v][1]+=maxt(d[u][0],d[u][1]+ch[u]);25         u=v;26     }27     if(choice){28         return maxt(d[u][0],d[u][1]+ch[u]);29     }30     else{31         return maxt(d[u][0],d[u][1]);32     }33 }34 35 long long sech(int f){36     int u=next[f];37     dp1[u][0]+=dp[f][0];38     dp1[u][1]+=dp[f][0];39     long long res1=dfs(f,u,dp1,false);40     dp[u][0]+=dp[f][1];41     dp[u][1]+=(dp[f][1]+ch[f]);42     long long res2=dfs(f,u,dp,true);43     return maxt(res1,res2);44 }45 46 int main(){47     while(scanf("%d",&N)!=EOF){48         top=0;49         memset(in,0,sizeof(in));50         memset(flag,false,sizeof(flag));51         for(int i=1;i<=N;i++){52             scanf("%d%d%d",&fr[i],&ch[i],&next[i]);53             in[next[i]]++;54             dp[i][0]=0;dp[i][1]=fr[i];55         }56         for(int i=1;i<=N;i++)57         if(in[i]==0)58         qt[++top]=i;59         while(top!=0){60             int u=qt[top--];61             int v=next[u];62             flag[u]=true;63             dp[v][1]+=maxt(dp[u][0],dp[u][1]+ch[u]);64             dp[v][0]+=maxt(dp[u][0],dp[u][1]);65             in[v]--;66             if(in[v]==0)67             qt[++top]=v;68         }69         long long sumt=0;70         memcpy(dp1,dp,sizeof(dp));71         for(int i=1;i<=N;i++){72             if(!flag[i]){73                 sumt+=sech(i);74             }75         }76         printf("%lld\n",sumt);77     }78     return 0;79 }
View Code


联系
我们