For each test case, output a line containing the minimum total coloring cost required for Bob to color all the nodes.
33
题意：
有一颗树，需要给他每个点都染色。节点标号从1-n，每个节点的权值在输入的第二行给出。 要求必须父节点已经染色，子节点才可以染色，需要按拓扑顺序染色。然后每个节点需要一个单位的染色时间。时间从1开始，计算费用时，每个节点的费用是当前时间*节点的权值。
第三行开始 接下来的输入是树的父亲和儿子的关系。
做法：
贪心，开始把每个点各自看成一个团。然后那个团的权值和 以及 这个团有多少个点 都记录在这个团的最顶上的祖先点上。 然后每次贪心 找 出（ 权值和/点数 ） 最大的那个团。然后用链表的记录方式 跟新 这个团的祖先 与 其父亲的关系。并把这个团 与那个父亲所在的团合并。
最后从root开始，历遍这个链表，时间从1开始，计算出总的花费。
为什么这么贪心，因为如果点多的团先连，就代表先走点多的团，花费的时间会更多，后面的花费会增加。 所以优先选择团是和点的数量成反比和团的总权值成正比的把。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map>
int w[1010];//团的权值
int root,num[1010];//团的点数
int n,c[1010]; //点的权值
int nex[1010],pre[1010]; //链表的记录
int fa[1010],vis[1010]; //父节点 和 有无访问过
int find()
{
double maxx=-1;
int id=-1;
for(int i=1;i<=n;i++)
{
if(i!=root&&(1.0*w[i]/num[i])>maxx&&!vis[i])
{
maxx=(1.0*w[i]/num[i]);
id=i;
}
}
vis[id]=1;
return id;
}
void unit(int p)
{
int i;
for(i=fa[p];~pre[i];i=pre[i]){} //找出父节点团的 祖先 也就是这个团中最先染色的点
w[i]+=w[p];
num[i]+=num[p];
for(i=fa[p];~nex[i];i=nex[i]){} //找出父节点团中 最后一个染色的点
pre[p]=i;
nex[i]=p;
}
int main ()
{
while(scanf("%d%d",&n,&root),n||root)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
c[i]=w[i];
num[i]=1;
pre[i]=nex[i]=-1;
vis[i]=0;
}
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
fa[v]=u;
}
while(1)
{
int tem=find();
if(tem==-1)
break;
unit(tem);
}
int time=1;
int ans=0;
for(int i=root;~i;i=nex[i])
{
ans+=time*c[i];
time++;
}
printf("%d\n",ans);
}
return 0;
}
/*
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0
*/
hdu 1055 & poj 2054 Color a Tree 树&贪心 找最大费用点和父节点合并
原文：http://blog.csdn.net/u013532224/article/details/44022095