2009年6月14日 星期日
題目鏈接：PKU 2054 Color a Tree
分類：一道漂亮的貪心（有點難度）
題目分析與算法模型
本題是一個比較難想的貪心，我是沒想到這樣的貪心方法，是看別人的報告后寫的，暈，由于while循環(huán)退出條件的疏忽，貢獻了無數(shù)次TLE，淚奔.......好了不說廢話了，先看一下這道題是怎么個貪心法：
這道題就是要求 Sigma( i * Ci ) (i = 1 .. n) 的值最小，{ Ci } 是節(jié)點費用的一個排列，同時要滿足父節(jié)點要出現(xiàn)在子節(jié)點前面。如果沒有父節(jié)點出現(xiàn)在子節(jié)點前面這個限制，那么答案很明顯。當{ Ci }按降序排列的時候，Sigma的值是最小的。當有這個限制的時候情況也是類似的。考慮某一個可行解，就是{ Ci }的某一個排列。找到其中的最大值，比如為Ck，它有一個父節(jié)點比如Cp。顯然Cp要出現(xiàn)在Ck之前。更進一步，Cp就應該出現(xiàn)在Ck的前一個位置。只有這樣才有可能Sigma的值最小。不然我們可以將Ck位置向前移動，得到一個更小的Sigma值，并且不破壞上面的約束。既然Cp就出現(xiàn)在Ck的前一個位置，那么它們其實就是連在一起的，可以最為一個整體來看。這樣問題的規(guī)模就有n減小到n-1。然后重復這一過程，直到所有的位置都確定下來。
算法流程：
1. 令所有節(jié)點S值均為1，每個節(jié)點生成序列中僅有一個元素，即為它本身。
2. 若樹中只剩一個結點，則輸出這個這個結點的生成序列。
3. 取出Ci/Si值最大的非根結點Max。
4. 將Max和其父親合并，新合并出的結點Union的各個參數(shù)為：Cunion=CMax+CPa(max)，SUnion=SMax+SPa(Max)，同時Union的生成序列為Pa(Max)的生成序列與Max的生成序列連接而成。
5. 重復2~4步。
注意：其實這題可以不用記錄結點先后的序列，設置一個全局變量res,在預處理時，res=所有節(jié)點的C的和，然后每合并兩個節(jié)點（編號為pos,其父節(jié)點為編號為f），那么res+=c[pos]*time[f],最后輸出res即可，至于為什么能這樣子，自己可以動腦筋思考一下
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