【解题报告】 POJ2054 给树染色
解题思路：
贪心
我们很容易想到从第一层开始，每次染权值最大的一个节点，但是我们可以构造出一个数，让一个权值很小的点下面有权值很大的节点，所以我们考虑的贪心思路是树中除了根节点外的权值最大的节点，它的父节点染色之后一定会被马上染色，所以我们可以将权值最大的点和它的父节点进行合并，合并得到的新点的权值是这两个点之和的平均值，这样就一直合并，直至合并到一个点的时候，我们就按照这个点合并的顺序染色就是正确的答案了。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <cstdio>
using namespace std;
long long r,n;
long long i,j,now,ans,a,b,father;
struct node
{
long long f,c,t;
double w;
}num[1010];
long long find()
{
long long ans=0;
double maxn=0;
for(int i=1;i<=n;i++)
{
if(i!=r&&num[i].w>maxn)
{
maxn=num[i].w;
ans=i;
}
}
return ans;
}
int main()
{
while(cin>>n>>r&&(n||r))
{
ans=0;
for(int i=1;i<=n;i++)
{
cin>>num[i].c;
num[i].w=num[i].c;
num[i].t=1;
ans+=num[i].c;
}
for(int i=1;i<=n-1;i++)
{
cin>>a>>b;
num[b].f=a;
}
for(int i=1;i<=n-1;i++)
{
now=find();
num[now].w=0;
father=num[now].f;
ans+=num[now].c*num[father].t;
for(int j=1;j<=n;j++)
{
if(num[j].f==now)
num[j].f=father;
}
num[father].c+=num[now].c;
num[father].t+=num[now].t;
num[father].w=(double)(num[father].c)/num[father].t;
}
cout<<ans<<endl;
}
return 0;
}
|
PS:LYD的代码有毒，在洛谷上过得了，但是在AcWing上过不了，所以我进行了摸爬滚打，终于找到了正确的答案，哈哈哈，我太开心了
