NOI 2002 贪吃的九头龙
This post is written in Chinese. Please consider using Google Translate
经典的树形动态规划题，涉及到了孩子之间的分配问题，需要用孩子兄弟表示法来实现。
首先，判断有解的条件是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]
/*
* 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;
}
<h2><span class="mw-headline">贪吃的九头龙 </span></h2>
【问题描述】
传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。
有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。
这M个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K个果子，而且K个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。
对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃 掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就 是所有头吃掉的树枝的“难受值”之和。
九头龙希望它的“难受值”尽量小，你能帮它算算吗？
例如图1所示的例子中，果树包含8个果子，7段树枝，各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋，大头需要吃掉4个果子，其中必须包含最大的果子。即N=8，M=2，K=4：
大头吃4个果子，用实心点标识；
小头吃4个果子，用空心点标识；
九头龙的难受值为4，因为图中用细边标记的树枝被大头吃掉了。
<a class="image" title="Image:Dragon.png" href="http://www.ruvtex.cn/wiki/Image:Dragon.png"><img src="http://www.ruvtex.cn/mw/images/c/c7/Dragon.png" alt="Image:Dragon.png" width="328" height="138" /></a>
图一描述了果树的形态，图二描述了最优策略。
【输入文件】
输入文件的第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。
【样例输入】
<pre>8 2 4
1 2 20
1 3 4
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5</pre>
【样例输出】
<pre>4</pre>
【样例说明】
该样例对应于题目描述中的例子。