贪心-poj-2054-Color a Tree - c++编程基础

题目大意：

给一颗树，每个节点有个权值Ci，求染色顺序，使得节点的染色时间Ti*Ci的总权值最小，其中要求对任意节点，只有当把父亲节点染完后，才能染该点。

解题思路：

比较巧妙的贪心。

分析知，权值大的肯定要先染，而要染它，必须先染其父亲，所以可以把它和其父亲放到一个集合里，然后将集合的总值/集合元素个数作为新的权值。

代码：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define LL long long  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#define M 1000000007  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 1100  
  
struct Edge  
{  
    int v;  
    struct Edge * next;  
}edge[Maxn],*head[Maxn];  
  
int num[Maxn],c[Maxn],cnt;  
int n,r,ans;  
int pre[Maxn];  
bool vis[Maxn];  
  
void add(int a,int b)  
{  
    ++cnt;  
    edge[cnt].v=b;  
    edge[cnt].next=head[a];  
    head[a]=&edge[cnt];  
}  
void unio(int fa,int cur)  
{  
    c[fa]+=c[cur];  //将cur集合连到fa集合上  
    num[fa]+=num[cur]; //个数也加过去  
  
    struct Edge * p=head[cur];  
  
    while(p)   //将cur的所有儿子的父亲都指向fa  
    {  
        int v=p->




v;  
        pre[v]=fa;  
        p=p->next;  
    }  
}  
int find()  
{  
    double tt=0;  
    int res;  
  
    for(int i=1;i<=n;i++)  //找到权值最大的节点  
    {  
        if(!vis[i]&&i!=r&&(double)c[i]/num[i]>tt)  
        {  
            tt=(double)c[i]/num[i];  
            res=i;  
        }  
    }  
    return res;  
}  
int Cal()  
{  
   for(int i=1;i