「树形DP」洛谷P2607 [ZJOI2008]骑士

2021-08-29 15:09:04

P2607 [ZJOI2008]骑士

题面：

题目描述

Z 国的骑士团是一个很有*的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。

最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。

骑士团是肯定具有打败邪恶*的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。

战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。

为了描述战斗力，我们将骑士按照 1 至 n 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

输入格式

第一行包含一个整数 n，描述骑士团的人数。

接下来 n 行，每行两个整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

输出格式

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

输入输出样例

输入 #1

3

10 2

20 3

30 1

输出 #1

说明/提示

数据规模与约定

对于 $30\%$ 的测试数据，满足 $n \le 10$；

对于 $60\%$的测试数据，满足 $n \le 100$；

对于 $80\%$ 的测试数据，满足 $n \le 10 ^4$。

对于 $100% $的测试数据，满足 $n \le 10^6$，每名骑士的战斗力都是不大于 $10^6$的正整数。

思路：

暴搜（显然是不可能的）

第一道基环树（环套树）上的DP问题，抛开这个问题，这道题就是没有上司的舞会（难怪考试时会想到骑士这道题），因为一个点有两种状态，要么在要么不在，这个点在，与他相邻的点就不在，这个点不在，与他相邻的点可能在也可能不在

状态转移方程：

$f[0][u]+=max(f[0][v],f[1][v])$

$f[1][u]+=f[0][v]$

下一个问题：这道题是一个连通图而不是树，该怎么处理？

1.建树：两种建树方法，都很巧妙（然而此前都没见过）

$①$ 建双向边，用位运算处理无向二元环

$②$ 建单向边，以厌恶的人为父亲节点，为什么能使用单向边：因为一定存在环，我们只要让有向边形成环就行了，同时我们在进行建树（删边）操作时又能保证环中一定存在根节点（因为每个人的出度都是1，根节点指向儿子节点，某一个其他的儿子节点（假如没有删边）又指向根节点，如果觉得我的说法模糊，可以移步洛谷第一篇题解，相当精彩：https://www.luogu.com.cn/problem/solution/P2607）

2.删边：

对于环套树的问题，肯定要转化为树，进而跑树形DP，所以对于每一个环，我们都断开一条边，对于边的两边的点分别跑一遍DP，最后取最大值（保证边两边的点不同时选）

代码：

/*#!/bin/sh

dir=$GEDIT_CURRENT_DOCUMENT_DIR

name=$GEDIT_CURRENT_DOCUMENT_NAME

pre=${name%.*}

g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11

if test $? -eq 0; then

    gnome-terminal -x bash -c "time $dir/$pre;echo;read;"

fi*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define int long long

using namespace std;

const int maxn=2e6+5,INF=0x3f3f3f3f;

int n,tot,vis[maxn],head[maxn],m,a[maxn],f[3][maxn],par[maxn],ans,rt;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();

	return s*w;

}

struct Edge{

	int next,to;

}e[maxn];

void Add(int x,int y){

	e[++tot].next=head[x];

	e[tot].to=y;

	head[x]=tot;

}

void DFS0(int u){

	vis[u]=1;

	f[1][u]=a[u];f[0][u]=0;//初始化，因为点u可能会重复经过

	for(int x=head[u];x;x=e[x].next){

		int v=e[x].to;

		if(v!=rt){

			DFS0(v);

			f[1][u]+=f[0][v];

			f[0][u]+=max(f[0][v],f[1][v]);

		}else{//说明跑到另一个根节点了

			f[1][v]=0;//强制不能选另一个根节点，因为删除的边两端的点不能同时选

		}

	}

}

void DFS(int u){

	vis[u]=1;

	while(!vis[par[u]]){

		u=par[u];

		vis[u]=1;

	}//跑整个连通区域

	rt=u;

	DFS0(u);

	int maxx=max(f[0][u],f[1][u]);

	u=par[u];rt=u;

	DFS0(u);

	ans+=max(maxx,max(f[0][u],f[1][u]));

}

signed main(){

	freopen("a.in","r",stdin);

	n=read();

	for(int i=1;i<=n;i++){

		a[i]=read();

		int y=read();

		Add(y,i);par[i]=y;//要是反着加就有问题了

	}

	for(int i=1;i<=n;i++){

		if(!vis[i])DFS(i);//跑每一个连通区域

	}

	cout<<ans;

}

OVER～

码农公寓