BZOJ 1040 [ZJOI2008]骑士 (基环树+树形DP)

时间:2023-12-18 21:29:44

<题目链接>

题目大意:

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

解题分析:

比较经典的基环树(环套树)。本题给出一个$n$条边$n$个点的有向图,我们可以发现,因为本题有向边表示这两个人至多只能出现其中一个,是用来表示一种关系的,所以在实际意义上,完全可以用无向边来代替。于是,本题就转化成了基环树森林,基环树的主要突破口就是要找出每个基环树的环(每个连通分量都是一颗基环树),然后将环中的一条边拆掉,使其变成一棵树,分别以拆掉的边的两个端点作为树的根,然后进行树形DP。本题就变成了对于树上有关系的两个点,只能选一个,使得最后的总价值最大,这就变成了一个比较经典的树形DP模型(比如上司的舞会)。

注意拆环的时候,强制一个点为根,并且不选,因为尽管我们拆除了那条边,但它还是正实存在的,所以只有不选的状态才能避免这两个点都被选中(防止违反题意)。

#include <bits/stdc++.h>
using namespace std; #define clr(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for(int i=s;i<=t;i++)
const int N = 1e6+;
typedef long long ll;
struct Edge{ int to,nxt; }e[N<<];
int n,m,cnt,head[N];
int Ecut,rt,urt;
int w[N],vis[N];
ll dp[N][]; inline void init(){
cnt=;clr(head,-);clr(vis,);clr(dp,);
}
inline void add(int u,int v){ e[cnt]=(Edge){ v,head[u] };head[u]=cnt++; } void dfs(int u,int pre){
vis[u]=;
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].to;
if(v==pre)continue;
if(!vis[v])dfs(v,u);
else { //如果找到环了
rt=u,urt=v,Ecut=i; //记录下这个环的两个端点,并且记录这个拆除的边
}
}
}
void trdp(int u,int pre){
dp[u][]=w[u]; //表示选当前这个点的价值
dp[u][]=; //表示不选当前这个点的价值
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].to;
if(i==Ecut || i==(Ecut^) || v==pre)continue;
trdp(v,u);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][],dp[v][]);
}
}
int main(){
while(~scanf("%d",&n)){
init();
REP(i,,n){
int now;scanf("%d%d",&w[i],&now);
add(i,now);add(now,i);
}
ll sum=;
REP(i,,n) if(!vis[i]) {
dfs(i,-); //基环树森林,每个连通分量中必有一个环
trdp(rt,-); //以拆分的两个点分别为根,进行树形DP
ll tmp = dp[rt][];
trdp(urt,-);
sum+=max(tmp,dp[urt][]);
}
printf("%lld\n",sum);
}
}