[ZJOI2008]骑士

题目描述

Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

输入格式

第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数

输出格式

应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

由于每个人都有一个憎恨对象，我们可以分析出这其实是一道基环树的题。那么根据基环树的套路，我们很明显是先处理环上点的子树，再处理环上部分。

考虑树上怎么做。显然树上的战力最大值具有传递性。那么我们可以用树形动规来解决问题。设dp(i,0/1)表示i的子树中战力的最大值，0表示i不选，1表示选。那么状态转移方程来了：

\[ dp[u][0]=\sum_{i=1}^{q}Max(dp[son[i]][0],dp[son[i]][1]);\dp[u][1]=\sum_{i=1}^{q}dp[son[i]][0] \]

初始化dp(u,1)=val(u)，val(u)表示u的战斗力。

然后考虑环上部分。我们参考着树上部分设计出一个状态：设f(i,0/1)表示i选与不选的最大值。如果你像往常那样试着列出状态转移方程，你会发现有点问题：

首先刚开始时是没什么毛病的：

\[ f[u][0]=Max(f[pre][0],f[pre][1])+dp[u][0];\f[u][1]=f[pre][0]+dp[u][1]; \]

但你发现到了环的最后一个点时，你可以计算出选择这个点的最大值，但你不知道这个值里面有没有包含选择环的起始点的值，如果有，那么恭喜你你错了，因为题目要求的是不能选连续的两个人。

所以仅仅这个小状态是不够的。我们不是需要知道起始点选不选吗？那就干脆再加一个：

设f(i,j,k)表示i的选择情况是k(k=0,1)，并且起始点的选择情况是j(j=0,1)时，战斗力的最大值。那么状态转移方程就可以列出来：

\[ f[u][0][0]=Max(f[pre][0][0],f[pre][0][1])+dp[u][0];\f[u][1][0]=Max(f[pre][1][0],f[pre][1][1])+dp[u][0];\f[u][0][1]=f[pre][0][0]+dp[u][1];\f[u][1][1]=f[pre][1][0]+dp[u][1]; \]

设环的起始点为s，那么只需初始化：

\[ f[s][0][0]=dp[s][0],f[s][1][1]=dp[s][1],dp[s][1][0]=dp[s][0][1]=-INF \]

设环的结束点为t，那么目标状态就是

\[ Max{\{}f[t][1][0],f[t][0][0],f[t][0][1]{\}} \]

总时间复杂度为O(N)

*不开long long见祖宗

*很容易写爆的基环树题

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000001
using namespace std;
 
struct edge{
    int to,next;
    edge(){}
    edge(const int &_to,const int &_next){ to=_to,next=_next; }
}e[maxn<<1];
int head[maxn],k;
 
int dfn[maxn],fa[maxn],tot;
bool inloop[maxn],vis[maxn],mark[maxn];
long long dp[maxn][2],f[maxn][2][2],ans;
int val[maxn],n;
 
inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
inline void add(const int &u,const int &v){ e[k]=edge(v,head[u]),head[u]=k++; }
 
void dfs_getloop(int u){
    dfn[u]=++tot;
    for(register int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]) continue;
        if(!dfn[v]) fa[v]=u,dfs_getloop(v);
        else if(dfn[u]<dfn[v]){
            inloop[v]=true;
            do{ inloop[fa[v]]=true,v=fa[v]; }while(v!=u);
        }
    }
}
void dfs_dp(int u){
    dp[u][1]=val[u],vis[u]=true;
    for(register int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(inloop[v]||vis[v]) continue;
        dfs_dp(v);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
void dp_loop(int u){
    bool flag=true; mark[u]=true;
    for(register int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(!inloop[v]||mark[v]) continue;
        f[v][0][0]=max(f[u][0][0],f[u][0][1])+dp[v][0],f[v][0][1]=f[u][0][0]+dp[v][1];
        f[v][1][0]=max(f[u][1][0],f[u][1][1])+dp[v][0],f[v][1][1]=f[u][1][0]+dp[v][1];
        dp_loop(v),flag=false;
    }
    if(flag) ans+=max(f[u][1][0],max(f[u][0][0],f[u][0][1]));
}
 
int main(){
    memset(head,-1,sizeof head);
    n=read();
    for(register int i=1;i<=n;i++){
        val[i]=read(); int v=read();
        add(v,i),add(i,v);
    }
    for(register int i=1;i<=n;i++) if(!dfn[i]) dfs_getloop(i);
    for(register int i=1;i<=n;i++) if(!vis[i]&&inloop[i]) dfs_dp(i);
    for(register int i=1;i<=n;i++) if(!mark[i]&&inloop[i])
        f[i][0][0]=dp[i][0],f[i][1][1]=dp[i][1],f[i][1][0]=f[i][0][1]=0x8080808080808080,dp_loop(i);
    printf("%lld\n",ans);
    return 0;
}

[ZJOI2008]骑士

原文：https://www.cnblogs.com/akura/p/10919980.html