BZOJ1040

发表于 | 分类于 |

题目传送门

Description

$Z$国有$N$个骑士，每个骑士有一个战斗力和一个讨厌的骑士（不会讨厌自己）。

骑士按$1$至$N$编号。

现在要选出一些骑士组成一个骑士团，要求骑士团内的每个骑士所讨厌的骑士都不在骑士团内。求：满足条件的骑士团的最大战斗力和是多少？

Input

第一行：一个数$N$，表示骑士数。

接下来$N$行：每行两个整数，分别表示当前骑士的战斗力和他讨厌的骑士的编号

Output

一个整数：表示最大战斗力和。

Solution

$A$讨厌$B$，则$AB$不能同时入选，等价于$B$讨厌$A$，所以应该是无向边。

一共有$N$个点$N$条边，很明显就是环套树。同一条边上的点不能同时入选，求最大和，显然用树形DP。

深搜一遍，发现环时就把环上的随便一条边拆掉，假设被拆掉的边的两个点分别为$u$和$v$，就在$u$和$v$上分别做树形DP。显然$u$和$v$不能同时选，所以比较一下两点中其中一个不取时的最大战斗力和，比较得出答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string.h>
#include<stack>
#include<queue>
using namespace std;
const int maxn=1000100;
int n,heat[maxn],zdl[maxn]; 
long long ans,sum;
struct EDGE
{
	int u,v,num;
	EDGE *next;
}edge[maxn*2],*ind[maxn];
int el=-1;
void input(int u,int v)
{
	edge[++el].u=u;
	edge[el].v=v;
	edge[el].num=el;
	edge[el].next=ind[u];
	ind[u]=&edge[el];
}
int visit[maxn],cuta,cutb,cute;
void dfs(int u,int fa)
{
	visit[u]=1;
	for(EDGE *k=ind[u];k!=NULL;k=k->next)
	{
		int v=k->v;
		if(v==fa) continue;
		if(visit[v])    //找到环
		{
			cuta=u;    //拆掉的边的两个点
			cutb=v;
			cute=k->num;
			continue;
		}
		dfs(v,u);
	}
}
long long int f[maxn],g[maxn];
long long dp(int u,int fa)      //树形DP
{
	f[u]=zdl[u];
	g[u]=0;
	for(EDGE *k=ind[u];k!=NULL;k=k->next)
	{
		int v=k->v;
		if(v==fa||k->num==cute||(k->num^1)==cute) continue;
		f[u]+=dp(v,u);
		g[u]+=max(f[v],g[v]);
	}
	return g[u];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&zdl[i],&heat[i]);
		input(heat[i],i);
		input(i,heat[i]);
	}
	for(int i=1;i<=n;i++)
	{
		if(visit[i]==0)
		{
			dfs(i,0);
			sum=max(dp(cutb,0),dp(cuta,0));
			ans+=sum;
		}
	}
	printf("%lld",ans);
	return 0;
}