pku2054 Color a Tree

#include<stdio.h>

const int MAXN=1005;
struct Node
{
    int parent,time,c;        //三个域分别表示父节点，当前集合的元素的个数，当前集合的总代价

    double weight;            //通过权重来设定涂色的优先级

};
Node node[MAXN];

int n,root;

int findMax()
{
    int position;
    double max=0;
    for(int i=1;i<=n;i++)
    {
        if(node[i].weight>max&&i!=root)        //查找能与父节点合并的子节点，但树根没有父节点            

        {
            position=i;
            max=node[i].weight;
        }
    }
    return position;
}

void setChild(int current)
{
    for(int i=1;i<=n;i++)
    {
        if(node[i].parent==current)
            node[i].parent=node[current].parent;    
    }
    
}

int main()
{

    while(scanf("%d%d",&n,&root),n+root)
    {
        int optimal=0;                
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&node[i].c);
            node[i].time=1;
            node[i].weight=node[i].c;

            optimal+=node[i].c;        //完成自身涂色所需的时间

        }

        for(int i=1;i<n;i++)
        {
            int v1,v2;
            scanf("%d%d",&v1,&v2);
            node[v2].parent=v1;
        }

        int set=n;
        while(set>1)                    
        {
            int position=findMax();
            int parent=node[position].parent;

            optimal+=node[position].c*node[parent].time;    
                //由于涂一个结点需要一个单位时间，故对于父节点而言time域表示该集合中的元素的个数

                //但对于子节点而言，计算轮到其涂色的时间为涂完父节点的时间和涂完自身所需的时间

                //而父节点的集合的元素个数标示涂完父节点的时间，涂完自身所需的时间已被初始化

                //该计算是处在相对环境下的，故不断累积相对父节点的时间


            setChild(position);
            node[parent].c+=node[position].c;
            node[parent].time+=node[position].time;
            node[parent].weight=node[parent].c*1.0/node[parent].time;
            node[position].weight=0;

            set--;
        }

        printf("%d\n",optimal);
    }
}

 

总结：该题采用贪心的思想，为了实现总体涂色代价最小则代价最大的节点必须先涂。在实际编程处理中不断将当前最大代价的节点同其父节点合并，而在计算时间时采用巧妙的计算方法。