Pku2054 Color a Tree

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

有一个N个结点的有根树，1是这个树的根。现在要对这N个结点依次进行
染色，每个结点染色要花费1个单位的时候，同时要满足一个结点仅在其
父亲被染色后才可被染色，每个结点有个权值Ci,如果我们在第Ti时间对
i号结点染色，则付出总代价为Sigma(Ti*Ci),1<=i<=N.
现在给出这个树和每个点的权值，请构造一种染色顺序，使得总代价最小.
N<=1000

5 1//5个点
1 2 1 2 4 //5个点的权值
1 2
1 3
2 4
3 5
0 0//整个测试结束
Sample Output
33

Sol:一个非常经典的贪心题.开始每个点i有其权值vi,大小为ti,每次找vi/ti最大的点进行染色，染色的代价为其父亲点所在块的大小。因为要先染其父亲点再染这个点。染完后将所有父亲点指i的，改为指向i的父亲点，并修改i的父亲点所在块的大小.因为数据范围太小了，所以没有用并查集了。这个题还有许多变形，后面再来补。

#include<bits/stdc++.h>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,r,x,y,fa[1010],v[1010];

double t[1010];

int main()

{

    while(1)

    {

        scanf("%d%d",&n,&r);

        if(n==0&&r==0)

        break;

        int ans=0,sum;

        double mx;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&v[i]);

            ans+=v[i];  //假设每个点都被首先染色过

            t[i]=1;

        }

        for(int i=1;i<n;i++)

        {

            scanf("%d%d",&x,&y);

            fa[y]=x;

        }

        for(int i=1;i<=n;i++)

        {

            mx=sum=0;

            for(int j=1;j<=n;j++)

            if(v[j]/t[j]>mx&&j!=r)

                    mx=v[j]/t[j],sum=j;

            for(int j=1;j<=n;j++) //将所有点，如果其父亲从前是sum,现在的父亲点改为fa[sum]

                  if(fa[j]==sum)

                     fa[j]=fa[sum];

            ans+=v[sum]*t[fa[sum]];

			 //取出这个点的权值，及它父亲点的t值，注意是父亲点的..

			 //也就是说当它父亲点染过后，它才被染，所以父亲点所在连通块有多少个点，它被染的序号就是乘上多少

            v[fa[sum]]+=v[sum];

            t[fa[sum]]+=t[sum];

            v[sum]=0;

        }

        printf("%d\n",ans);

    }

    return 0;

}