Beyond the Void
BYVoid
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&lt;=N&lt;=300),M (2&lt;=M&lt;=N),K (1&lt;=K&lt;=N)。 N個果子依次編號1,2,...,N,且最大的果子的編號總是1。第2行到第N行描述了果樹的形態,每行包含三個整數a (1&lt;=a&lt;=N),b (1&lt;=b&lt;=N),c (0&lt;=c&lt;=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

相關日誌