题目链接:http://poj.org/problem?id=2054

    题目大意:给一棵树,为每个顶点着色,可着色的条件是,当前着色点的父结点已着色。求所有结点的最小

花费和,每个点的着色最小花费应该是顶点权值和它着色完时间的乘积。

    题意分析:贪心呀、、、这个题大家都说合并结点,但我理解起来有点困难,想不明白未什么说是合并结点。我觉得其实就是对一棵树进行拓扑排序,找出所有拓扑排序中最小的着色花费和。分析到这呢,看看数据范围,结点最多的时候有1000,所以,要是深搜,超时的可能性极大。再深入分析一下,应该优先染哪种点,才会使花费和最小?是不是应该尽量先染权值大的?问题又来了,那是不是说按权值从大到小染?因为要给某个结点染色,父结点必须着色,也就是说染色仅仅判断权值是不够的,那应该考虑什么?我姑且称之为性价比吧.



代码如下:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAXN 1010

int n, r;
int w[MAXN]; 

   //结点的权值
int parent[MAXN];    //结点的父结点
int vis[MAXN];    //标记结点
int next[MAXN];    //记录结点的下一个该染的点
int pre[MAXN];     //记录要染哪个结点前必须染的点
int rank[MAXN];    //点的优先级别
int sum[MAXN];    //合并子结点后的权值

//找当前性价比最大的结点
int Find(){
    double max = 0;
    int flag = -1;
    int i;
    for( i=1; i<=n; i++ ){
        if( !vis[i] && max < (double) sum[i] / rank[i] ){
            max = (double) sum[i] / rank[i];
            flag = i;
        }
    }
    return flag;
}

//更新值,找染色顺序
void Union( int x ){
    int i;
    for( i=parent[x]; pre[i]!=-1; i = pre[i] )
        ;
    rank[i] += rank[x];
    sum[i] += sum[x];
    for( i=parent[x]; next[i]!=-1; i=next[i] )
        ;
    next[i] = x;
    pre[x] = i;
    vis[x] = 1;
}

int main(){
    int u,v;
    int ans,cnt;
    int i;
    while( scanf( "%d %d", &n,&r )==2 && (n+r) ){
        for( i=1; i<=n; i++ ){
            scanf("%d", &w[i]);
            vis[i] = 0;
            pre[i] = next[i] = -1;
            rank[i] = 1;
            sum[i] = w[i];
        }
        for( i=1; i<n; i++ ){
            scanf( "%d %d",&u,&v );
            parent[v] = u;
        }
        vis[r] = 1;
        while( 1 ){
            u = Find();
            if( u == -1 )
                break;
            Union( u );
        }
        cnt = 0;
        ans = 0;
        for( i=r; i!=-1; i=next[i] ){
            cnt++;
            ans += cnt * w[i];
        }
        printf( "%d\n",ans );
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation