洛谷P2607 [ZJOI2008]骑士

@Pelom  October 12, 2021

题意:

求基环树最大带权独立集。

数据范围: $N \le 1000000$

题解:

算法:树形dp

分析题意:由“每个骑士都有且仅有一个自己最厌恶的骑士(当然不是他自己)”建立有向图,将每个人 $x$ 最厌恶的人 $y$ 记为其父节点 $fa[x]=y$ ,可得每个节点有且仅有一条出边,且无自环。由于共有 $N$ 条边,所以该图为基环树。

考虑到基环树的性质,删边后必定构成一棵树。分别以删去的边连接的两端点为根节点对新树进行dp(注意不能这两个端点不能同时选),再对两个结果取最大值。用 $dp[u][0/1]$ 表示以$u$为根节点的子树不选/选 $u$ 的最大值。可以得出状态转移方程:

$$dp[u][0]= \sum max(dp[v][0],dp[u][1])$$

$$dp[u][1]= \sum max(dp[v][0])$$

其中 $v$ 为 $u$ 的子节点。

此外,注意开 $long\ long$。

代码:

#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
const int N=1000010;
struct edge{
    int nxt,to;
}e[N];
int n,a;
int cnt,rt;
LL ans;
int c[N],head[N],fa[N];
LL dp[N][2];
bool vis[N];
template <typename T>
inline T Max(T a,T b){
    return a>b?a:b;
}
inline void add(int u,int v){
    e[++cnt]=(edge){head[u],v};
    head[u]=cnt;
}
void dfs(int u){
    vis[u]=1;
    dp[u][0]=0,dp[u][1]=c[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=rt){
            dfs(v);
            dp[u][0]+=Max(dp[v][0],dp[v][1]);
            dp[u][1]+=dp[v][0];
        }
        else dp[v][1]=-N;
    }
}
inline void findC(int u){
    vis[u]=1;
    rt=u;
    for(;!vis[fa[rt]];){
        rt=fa[rt];
        vis[rt]=1;
    }
    dfs(rt);
    LL t=Max(dp[rt][0],dp[rt][1]);
    vis[rt]=1;
    rt=fa[rt];
    dfs(rt);
    ans+=Max(t,Max(dp[rt][0],dp[rt][1]));
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&c[i],&a);
        add(a,i);
        fa[i]=a;
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
            findC(i);
    printf("%lld",ans);
    return 0;
}

添加新评论