P2607 [ZJOI2008] 骑士

方杰123 · 2022-10-14 12:22:44 · 个人记录

题目

思路

还是这张图，这题读入方式和这题一样。所以代码结构上很像。

1. 把环上每个点看做树根，往环外做树形DP。
2. 任意找到环上一点，遍历一遍。处理一下首尾的关系。
3. 用拓扑实现起来简单。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+10;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int dp[N][2],n,va[N],to[N],ind[N],f[N][2],f2[N][2],ans;
queue<int>q;
int work(int u){
    int now=u;
    f[u][1]=dp[u][1],f[u][0]=-1e15;//选第一个点
    f2[u][1]=-1e15,f2[u][0]=dp[u][0];//不选第一个点
    while(to[now]!=u){ind[now]=0;
        f[to[now]][0]+=max(f[now][0],f[now][1])+dp[to[now]][0];
        f[to[now]][1]+=f[now][0]+dp[to[now]][1];
        f2[to[now]][0]+=max(f2[now][0],f2[now][1])+dp[to[now]][0];
        f2[to[now]][1]+=f2[now][0]+dp[to[now]][1];
        now=to[now];
    }
    ind[now]=0;
    return max(f[now][0],max(f2[now][0],f2[now][1]));
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)va[i]=read(),to[i]=read(),ind[to[i]]++;
    for(int i=1;i<=n;i++){dp[i][1]=va[i];if(!ind[i])q.push(i);}
    while(!q.empty()){
        int u=q.front();q.pop();
        dp[to[u]][0]+=max(dp[u][1],dp[u][0]);
        dp[to[u]][1]+=dp[u][0];
        ind[to[u]]--;if(!ind[to[u]])q.push(to[u]);
    }
    for(int i=1;i<=n;i++)if(ind[i])ans+=work(i);
    printf("%lld\n",ans);
    return 0;
}