贪心-poj-2054-Color a Tree

题目大意：

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

解题思路：

比较巧妙的贪心。

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

代码：

#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<sstream>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#include<ctime>  
#include<bitset>  
#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<n;i++)  
   {  
       int cur=find(); //找到后  
  
       vis[cur]=true;  //标记  
       int fa=pre[cur]; //找出其父亲  
  
       while(vis[fa])  //如果父亲已访问  
            fa=pre[fa]; //直到找到没有被访问的父亲  
      ans+=c[cur]*num[fa]; //加上合并的权值  
      unio(fa,cur);  
  
   }  
   return ans+c[r];  
}  
  
int main()  
{  
   while(scanf("%d%d",&n,&r)&&n+r)  
   {  
       for(int i=1;i<=n;i++)  
       {  
           scanf("%d",&c[i]);  
           num[i]=1;  
       }  
  
       memset(head,NULL,sizeof(head));  
       memset(vis,false,sizeof(vis));  
       cnt=0;  
  
       for(int i=1;i<n;i++)  
       {  
           int a,b;  
           scanf("%d%d",&a,&b);  
           add(a,b);  
           pre[b]=a;  
       }  
       ans=0;  
       printf("%d\n",Cal());  
   }  
   return 0;  
}

补充：软件开发 , C++ ,