2009年6月14日 星期日
题目链接：PKU 2054 Color a Tree
分类：一道漂亮的贪心（有点难度）
题目分析与算法模型
本题是一个比较难想的贪心，我是没想到这样的贪心方法，是看别人的报告后写的，晕，由于while循环退出条件的疏忽，贡献了无数次TLE，泪奔.......好了不说废话了，先看一下这道题是怎么个贪心法：
这道题就是要求 Sigma( i * Ci ) (i = 1 .. n) 的值最小，{ Ci } 是节点费用的一个排列，同时要满足父节点要出现在子节点前面。如果没有父节点出现在子节点前面这个限制，那么答案很明显。当{ Ci }按降序排列的时候，Sigma的值是最小的。当有这个限制的时候情况也是类似的。考虑某一个可行解，就是{ Ci }的某一个排列。找到其中的最大值，比如为Ck，它有一个父节点比如Cp。显然Cp要出现在Ck之前。更进一步，Cp就应该出现在Ck的前一个位置。只有这样才有可能Sigma的值最小。不然我们可以将Ck位置向前移动，得到一个更小的Sigma值，并且不破坏上面的约束。既然Cp就出现在Ck的前一个位置，那么它们其实就是连在一起的，可以最为一个整体来看。这样问题的规模就有n减小到n-1。然后重复这一过程，直到所有的位置都确定下来。
算法流程：
1. 令所有节点S值均为1，每个节点生成序列中仅有一个元素，即为它本身。
2. 若树中只剩一个结点，则输出这个这个结点的生成序列。
3. 取出Ci/Si值最大的非根结点Max。
4. 将Max和其父亲合并，新合并出的结点Union的各个参数为：Cunion=CMax+CPa(max)，SUnion=SMax+SPa(Max)，同时Union的生成序列为Pa(Max)的生成序列与Max的生成序列连接而成。
5. 重复2~4步。
注意：其实这题可以不用记录结点先后的序列，设置一个全局变量res,在预处理时，res=所有节点的C的和，然后每合并两个节点（编号为pos,其父节点为编号为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