NOI 2002 貪喫的九頭龍
本文正體字版由OpenCC轉換
經典的樹形動態規劃題，涉及到了孩子之間的分配問題，需要用孩子兄弟表示法來實現。
首先，判斷有解的條件是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>
【樣例說明】
該樣例對應於題目描述中的例子。
上次修改時間 2017-05-22