[BZOJ1040/Luogu2607][ZJOI2008]骑士

题目链接：

BZOJ1040

Luogu2607

第一眼看题目：最大独立点集？秒了！

看数据范围：\(1e6\)？自闭了

贪心？这种题显然不能贪心吧。。

把题目转成图：每个人有一条出边连向他人。

那么就是个基环树森林。。

然后再看题目模型。。。woc，上司的舞会？

那么这就是基环树\(DP\)了。

对于每一个环，选一条环上的边\((x,y)\)断开。

设\(f_{x,0/1}\)表示以\(x\)为根的子树内，不选/选\(x\)的最大战斗力。

答案就是\(\max\{f_{x,0},f_{y,0}\}\)（总有一个点不能选）。

这里我用并查集来找环，虽然慢了一些（\(Luogu\)最后一点\(973ms\)），但是好写。强烈推荐

什么，不会树形\(DP\)?

转移式：

\[f_{x,0}=\sum\max\{f_{y,0},f_{y,1}\}\]

\[f_{x,1}=\sum f_{y,0}\]

时间复杂度 \(O(n\alpha(n))\)

#include <cstdio>
#include <cctype>
typedef long long ll;

inline ll Max(ll a,ll b){return a>b?a:b;}
inline int Getint()
{
    register int x=0,c;
    while(!isdigit(c=getchar()));
    for(;isdigit(c);c=getchar())x=x*10+(c^48);
    return x;
}

int n,Att[1000005],Fa[1000005],Ls[1000005],Rs[1000005],Cs;
int Head[1000005],Next[2000005],To[2000005],En;
ll f[1000005][2],Ans;

inline void Add(int x,int y)
{Next[++En]=Head[x],To[Head[x]=En]=y;}
int Get(int x){return x==Fa[x]?x:Fa[x]=Get(Fa[x]);}

void DP(int x,int Pre)
{
    f[x][0]=0,f[x][1]=Att[x];
    for(int i=Head[x],y;i;i=Next[i])
        if((y=To[i])!=Pre)
        {
            DP(y,x);
            f[x][0]+=Max(f[y][0],f[y][1]);
            f[x][1]+=f[y][0];
        }
}

int main()
{
    n=Getint();
    for(int i=1;i<=n;++i)Fa[i]=i;
    for(int i=1,x;i<=n;++i)
    {
        Att[i]=Getint(),x=Getint();
        int Fx=Get(i),Fy=Get(x);
        if(Fx==Fy)Ls[++Cs]=i,Rs[Cs]=x;
        else Add(i,x),Add(x,i),Fa[Fx]=Fy;
    }
    for(int i=1;i<=Cs;++i)
    {
        DP(Ls[i],0);
        ll v=f[Ls[i]][0];
        DP(Rs[i],0);
        Ans+=Max(v,f[Rs[i]][0]);
    }
    printf("%lld\n",Ans);
    return 0;
}

[BZOJ1040/Luogu2607][ZJOI2008]骑士

原文：https://www.cnblogs.com/LanrTabe/p/10165118.html