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é)點前面這個限制，那么答案很明顯。當(dāng){ Ci }按降序排列的時候，Sigma的值是最小的。當(dāng)有這個限制的時候情況也是類似的。考慮某一個可行解，就是{ Ci }的某一個排列。找到其中的最大值，比如為Ck，它有一個父節(jié)點比如Cp。顯然Cp要出現(xiàn)在Ck之前。更進一步，Cp就應(yīng)該出現(xiàn)在Ck的前一個位置。只有這樣才有可能Sigma的值最小。不然我們可以將Ck位置向前移動，得到一個更小的Sigma值，并且不破壞上面的約束。既然Cp就出現(xiàn)在Ck的前一個位置，那么它們其實就是連在一起的，可以最為一個整體來看。這樣問題的規(guī)模就有n減小到n-1。然后重復(fù)這一過程，直到所有的位置都確定下來。

算法流程：

1.        令所有節(jié)點S值均為1，每個節(jié)點生成序列中僅有一個元素，即為它本身。

2.        若樹中只剩一個結(jié)點，則輸出這個這個結(jié)點的生成序列。

3.        取出Ci/Si值最大的非根結(jié)點Max。

4.        將Max和其父親合并，新合并出的結(jié)點Union的各個參數(shù)為：Cunion=CMax+CPa(max)，SUnion=SMax+SPa(Max)，同時Union的生成序列為Pa(Max)的生成序列與Max的生成序列連接而成。

5.        重復(fù)2~4步。

注意：其實這題可以不用記錄結(jié)點先后的序列，設(shè)置一個全局變量res,在預(yù)處理時，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