五 18

NOI 2002 贪吃的九头龙

NOI Add comments154 views

经典的树形动态规划题，涉及到了孩子之间的分配问题，需要用孩子兄弟表示法来实现。

首先，判断有解的条件是M-1<=N-K。由于2<=M<=N，当M=2时，相当于把所有节点染上不同颜色，两端颜色相 同的边要被算上权值，求权值最小的方案。假定“大头”要吃的节点为黑色节点，其余为白色节点。我们需要考虑所有的两端颜色相同的边。如果M>2，则 只需要考虑两端都是黑色的边。因为当剩余颜色多于1时，一定可以找到一种方案，使得“小头”不会吞下树枝。

定义i.son为i的第一个孩子，i.brother为i的兄弟节点，i.cost为i向其父亲连接的边的权值。

状态定义

F[i][j][k]为以i为根的子树及以其右边的兄弟为根的子树中，有j个节点被染黑，且i的父亲节点的颜色为k(1为黑色，0为其它)时的最小费用

状态转移方程

F[i][j][k]=Min
{
	F[i.son][j'][0] + F[i.brother][j-j'][k] + D(0,k) * i.cost,
	F[i.son][j'][1] + F[i.brother][j-j'-1][k] + D(1,k) * i.cost,
}

其中 D(a,b)表示两端颜色为a,b之间的边是否要被吃掉，具体定义为

D(a,b) =
{
	1 | a=b=1
	1 | a=b=0 且 M=2
	0 | 其它情况
}

边界条件

节点0表示一个虚拟的空节点

F[0][0][k] = 0 (k=0,1)

F[0][j][k] = 无穷大 (j>0 k=0,1)

目标状态

F[节点1.son][K-1][1]

?View Code CPP
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

/* 
 * Problem: NOI2002 dragon
 * Author: Guo Jiabao
 * Time: 2009.5.18 14:02
 * State: Solved
 * Memo: 树形动态规划 孩子兄弟分配问题
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=301,INF=0x7FFFFFF;
using namespace std;
struct edge
{
	edge *next;
	int t,c;
}*V[MAXN],ES[MAXN*2];
struct node
{
	int son,brother,cost;
}T[MAXN];
int N,M,K,EC,Ans,Stack[MAXN];
bool vis[MAXN];
int F[MAXN][MAXN][2];
inline void addedge(int a,int b,int c)
{
	ES[++EC].next = V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next = V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=c;
}
void maketree()
{
	int i,j,Stop;
	Stack[Stop=1]=1;
	while (Stop)
	{
		i=Stack[Stop--];
		vis[i]=true;
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (!vis[j])
			{
				T[j].brother=T[i].son;
				T[j].cost=e->c;
				T[i].son=j;
				Stack[++Stop]=j;
			}
		}
	}
}
void init()
{
	int i,a,b,c;
	freopen("dragon.in","r",stdin);
	freopen("dragon.out","w",stdout);
	scanf("%d%d%d",&N,&M,&K);
	for (i=1;i<N;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
	maketree();
	memset(F,-1,sizeof(F));
}
inline int D(int a,int b)
{
	return ((a==1 && b==1)||(a==0 && b==0 && M==2));
}
int DP(int i,int j,int k)
{
	if (F[i][j][k]==-1)
	{
		int a,v,rs=INF;
		for (a=0;a<=j;a++)
		{
			v = DP(T[i].son,a,0) + DP(T[i].brother,j-a,k) + D(0,k) * T[i].cost;
			if (v<rs) rs=v;
			if (a<j)
			{
				v = DP(T[i].son,a,1) + DP(T[i].brother,j-a-1,k) + D(1,k) * T[i].cost;
				if (v<rs) rs=v;
			}
		}
		F[i][j][k]=rs;
 
	}
	return F[i][j][k];
}
void solve()
{
	if (M-1 <= N-K)
	{
		F[0][0][0]=F[0][0][1]=0;
		for (int i=1;i<=K;i++)
			F[0][i][0]=F[0][i][1]=INF;
		Ans=DP(T[1].son,K-1,1);
	}
	else
		Ans=-1;
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}

贪吃的九头龙

【问题描述】

传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。

有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。

这M个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K个果子，而且K个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。

对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃 掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就 是所有头吃掉的树枝的“难受值”之和。

九头龙希望它的“难受值”尽量小，你能帮它算算吗？

例如图1所示的例子中，果树包含8个果子，7段树枝，各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋，大头需要吃掉4个果子，其中必须包含最大的果子。即N=8，M=2，K=4：

大头吃4个果子，用实心点标识；

小头吃4个果子，用空心点标识；

九头龙的难受值为4，因为图中用细边标记的树枝被大头吃掉了。

Image:Dragon.png

图一描述了果树的形态，图二描述了最优策略。

【输入文件】

输入文件的第1行包含三个整数N (1<=N<=300)，M (2<=M<=N)，K (1<=K<=N)。 N个果子依次编号1,2,…,N，且最大的果子的编号总是1。第2行到第N行描述了果树的形态，每行包含三个整数a (1<=a<=N)，b (1<=b<=N)，c (0<=c<=105)，表示存在一段难受值为c的树枝连接果子a和果子b。

【输出文件】

输出文件仅有一行，包含一个整数，表示在满足“大头”的要求的前提下，九头龙的难受值的最小值。如果无法满足要求，输出-1。

【样例输入】

8 2 4
1 2 20
1 3 4
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5

【样例输出】

4

【样例说明】

该样例对应于题目描述中的例子。

Maybe you like

标签：, ,


Leave a Reply

37 queries. 0.620 seconds. Designed by NattyWP .
Images by desEXign.