2009年6月14日 星期日
題目鏈接：PKU 2054 Color a Tree
分類：一道漂亮的貪心（有點(diǎn)難度）
題目分析與算法模型
本題是一個(gè)比較難想的貪心，我是沒(méi)想到這樣的貪心方法，是看別人的報(bào)告后寫的，暈，由于while循環(huán)退出條件的疏忽，貢獻(xiàn)了無(wú)數(shù)次TLE，淚奔.......好了不說(shuō)廢話了，先看一下這道題是怎么個(gè)貪心法：
這道題就是要求 Sigma( i * Ci ) (i = 1 .. n) 的值最小，{ Ci } 是節(jié)點(diǎn)費(fèi)用的一個(gè)排列，同時(shí)要滿足父節(jié)點(diǎn)要出現(xiàn)在子節(jié)點(diǎn)前面。如果沒(méi)有父節(jié)點(diǎn)出現(xiàn)在子節(jié)點(diǎn)前面這個(gè)限制，那么答案很明顯。當(dāng){ Ci }按降序排列的時(shí)候，Sigma的值是最小的。當(dāng)有這個(gè)限制的時(shí)候情況也是類似的。考慮某一個(gè)可行解，就是{ Ci }的某一個(gè)排列。找到其中的最大值，比如為Ck，它有一個(gè)父節(jié)點(diǎn)比如Cp。顯然Cp要出現(xiàn)在Ck之前。更進(jìn)一步，Cp就應(yīng)該出現(xiàn)在Ck的前一個(gè)位置。只有這樣才有可能Sigma的值最小。不然我們可以將Ck位置向前移動(dòng)，得到一個(gè)更小的Sigma值，并且不破壞上面的約束。既然Cp就出現(xiàn)在Ck的前一個(gè)位置，那么它們其實(shí)就是連在一起的，可以最為一個(gè)整體來(lái)看。這樣問(wèn)題的規(guī)模就有n減小到n-1。然后重復(fù)這一過(guò)程，直到所有的位置都確定下來(lái)。
算法流程：
1. 令所有節(jié)點(diǎn)S值均為1，每個(gè)節(jié)點(diǎn)生成序列中僅有一個(gè)元素，即為它本身。
2. 若樹(shù)中只剩一個(gè)結(jié)點(diǎn)，則輸出這個(gè)這個(gè)結(jié)點(diǎn)的生成序列。
3. 取出Ci/Si值最大的非根結(jié)點(diǎn)Max。
4. 將Max和其父親合并，新合并出的結(jié)點(diǎn)Union的各個(gè)參數(shù)為：Cunion=CMax+CPa(max)，SUnion=SMax+SPa(Max)，同時(shí)Union的生成序列為Pa(Max)的生成序列與Max的生成序列連接而成。
5. 重復(fù)2~4步。
注意：其實(shí)這題可以不用記錄結(jié)點(diǎn)先后的序列，設(shè)置一個(gè)全局變量res,在預(yù)處理時(shí)，res=所有節(jié)點(diǎn)的C的和，然后每合并兩個(gè)節(jié)點(diǎn)（編號(hào)為pos,其父節(jié)點(diǎn)為編號(hào)為f），那么res+=c[pos]*time[f],最后輸出res即可，至于為什么能這樣子，自己可以動(dòng)腦筋思考一下
Code:
1
#include<stdio.h>
2#include<string.h>
3#define max 1100
4
5int n,r,i,v1,v2,j,res,pos,f;
6struct node
7
{
8
int c,time,parent;
9 double w;
10
}Node[max];
11
12int find()
13{
14 int i,m;
15 double Max=0;
16 for(i=1;i<=n;i++)
17 if(Node[i].w>Max&&i!=r)
18
{
19 Max=Node[i].w;
20 m=i;
21
}
22 return m;
23}
24
25int main()
26{
27 while(scanf("%d%d",&n,&r)!=EOF)
28 {
29 if(!n&&!r)break;
30 res=0;
31 for(i=1;i<=n;i++)
32 {
33 Node[i].time=1;
34 scanf("%d",&Node[i].c);
35 Node[i].w=Node[i].c;
36 res+=Node[i].c;
37 }
38 for(i=1;i<=n-1;i++)
39 {
40 scanf("%d%d",&v1,&v2);
41 Node[v2].parent=v1;
42 }
43 Node[r].parent=-1;
44 int count=n;
45 while(count>1)
46 {
47 pos=find();
48 f=Node[pos].parent;
49 res+=Node[pos].c*Node[f].time;
50 for(j=1;j<=n;j++)
51 if(Node[j].parent==pos)Node[j].parent=f;
52 Node[pos].w=0;
53 Node[f].time+=Node[pos].time;
54 Node[f].c+=Node[pos].c;
55 Node[f].w=(double)Node[f].c/Node[f].time;
56 count--;
57 }
58 printf("%d\n",res);
59 }
60 return 0;
61}
62
63