文档章节

poj 2054 Color a Tree

locusxt
 locusxt
发布于 2014/03/22 11:06
字数 1727
阅读 834
收藏 1

小班课讲了这道题,贪心


题意:

有一棵树,需要给其所有节点染色,每个点染色所需的时间是一样的都是1.给每个点染色,还有一个开销“当前时间×ci”,ci是每个节点的一个权值。
染色还有另一个约束条件,要染一个点必须要先染好其父节点,所以第一个染的点是根节点。
求最小开销。


Color a Tree
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 6811 Accepted: 2318

Description

Bob is very interested in the data structure of a tree. A tree is a directed graph in which a special node is singled out, called the "root" of the tree, and there is a unique path from the root to each of the other nodes. 

Bob intends to color all the nodes of a tree with a pen. A tree has N nodes, these nodes are numbered 1, 2, ..., N. Suppose coloring a node takes 1 unit of time, and after finishing coloring one node, he is allowed to color another. Additionally, he is allowed to color a node only when its father node has been colored. Obviously, Bob is only allowed to color the root in the first try. 

Each node has a "coloring cost factor", Ci. The coloring cost of each node depends both on Ci and the time at which Bob finishes the coloring of this node. At the beginning, the time is set to 0. If the finishing time of coloring node i is Fi, then the coloring cost of node i is Ci * Fi. 

For example, a tree with five nodes is shown in Figure-1. The coloring cost factors of each node are 1, 2, 1, 2 and 4. Bob can color the tree in the order 1, 3, 5, 2, 4, with the minimum total coloring cost of 33. 

Given a tree and the coloring cost factor of each node, please help Bob to find the minimum possible total coloring cost for coloring all the nodes.

Input

The input consists of several test cases. The first line of each case contains two integers N and R (1 <= N <= 1000, 1 <= R <= N), where N is the number of nodes in the tree and R is the node number of the root node. The second line contains N integers, the i-th of which is Ci (1 <= Ci <= 500), the coloring cost factor of node i. Each of the next N-1 lines contains two space-separated node numbers V1 and V2, which are the endpoints of an edge in the tree, denoting that V1 is the father node of V2. No edge will be listed twice, and all edges will be listed. 

A test case of N = 0 and R = 0 indicates the end of input, and should not be processed. 

Output

For each test case, output a line containing the minimum total coloring cost required for Bob to color all the nodes.

Sample Input

5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0

Sample Output

33

Source

[Submit]   [Go Back]   [Status]   [Discuss]

解法:

小班课比较详细地给出了解法和证明。
(以下已经把每个点看成一个点集,独立的一个点可看做只有一个元素的点集,每个点集中的点有顺序,并且需要依次连续地染色,也就是染完第一个点后,需要立刻依次染之后的点)
每次找一个最大权值的非根点集,将它和它的父点集合并。新的点集的权值是(新点集中所有点的权值和)/(新点集中点的个数)。这里点集中的点有顺序,合并时,子点集的点放在父点集的点后面。
进行上述步骤,直到只剩下一个根点集。这时候,根点集中点的顺序,就是染色的顺序。



证明:

(i)先看每个都是点的情况。给出一个结论:如果这棵树中有最大权值点x(非根),那么一旦x的父节点已经染色,就应该立刻染x。
这比较好证:设x的父节点为y,染色顺序为ya...bx,a...b这一段是别的一些可以染的点。这个染色顺序的意思是说染完x的父节点y之后,先染了一些别的点,再染x。
如果我们把b和x的染色顺序交换,显然是可行的,并且会更优:比较xb和bx,使用前者我们的收益(少掉的开销)是Cx-Cb,x少等了1的时间,b多等了1的时间。显然,收益Cx-Cb是正的,因为x的权值是当前最大的。这样我们也可以证,染完y之后应该立刻染x,所以可以把y和x合并成一个点集。
(ii)现在看都看做点集的情况,证明合并后以平均权值作为新的权值是合理的。
一个结论:如果这棵树中有最大平均权值点集X(非根),那么一旦X的父点集已经染色,就应该立刻染X。
这和(i)类似:设X的父子集Y,染色顺序YA...BX,A...B是别的一些可以染的点集。下证B和X染色顺序互换可以更优。设B的总权值为SB,点数为NB;X的为SX和NX。XB和BX比较,使用前者的收益是SX×NB- SB×NX,这相当与X中的每个点都少等待NB时间,而B中的每个点都多等了NX的时间。又因为X是最大平均权值点集,所以权值SX/NX>SB/NB,所以可以确保收益SX×NB-SB×NX是正的。
所以这样合并没有问题。


代码:

#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#define maxn 1005
using namespace std;

class node
{
	public:
		int value_sum;//点集中所有点的权值和
		int num;//点集中点的个数
		int father;
		int set_id;//所属点集编号
		bool is_setrep;//是不是点集的首个元素
		double value;//权值平均
		vector<int> in_set;//点集中其他点
		vector<int> son;//该点集的子点集

		node()
		{
			num = 1;
			father = -1;
			is_setrep = true;
		}
};

node no[maxn];
int seq[maxn] = {0};//最后的涂的顺序的序列
int c[maxn] = {0};//涂每个点的花费

int n = 0, r = 0;

void init()
{
	memset(no, 0, sizeof(no));
	for (int i = 1; i <= n; ++i)
	{
			no[i].num = 1;
			no[i].father = -1;
			no[i].is_setrep = true;
	}
}

//将编号为a的点集与其父点集合并
void union_node(int a)
{
	int fa = no[a].father;
	int son_num = no[a].son.size();
	//printf("sonnum: %d\n", son_num);
	no[fa].value_sum += no[a].value_sum;
	no[fa].num += no[a].num;
	no[fa].value = (double)(no[fa].value_sum) / no[fa].num;
	no[a].set_id = fa;
	no[a].is_setrep = false;
	no[fa].in_set.push_back(a);
	//printf("value: %f\n", no[fa].value);
	for (int i = 0; i < no[a].num - 1; ++i)
	{
		no[fa].in_set.push_back(no[a].in_set[i]);
		no[no[a].in_set[i]].set_id = fa;
	}
	for (int i = 0; i < son_num; ++i)
	{
		no[no[a].son[i]].father = fa;
		no[fa].son.push_back(no[a].son[i]);
	}
}

int main()
{
	while(true)
	{
		scanf("%d%d", &n, &r);
		init();
		if (n == 0)
			break;
		int tmp = 0;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &tmp);
			c[i] = tmp;
			no[i].value = no[i].value_sum = tmp;
			no[i].set_id = i;
		}

		int tmp1 = 0, tmp2 = 0;
		for (int i = 0; i < n - 1; ++i)
		{
			scanf("%d%d", &tmp1, &tmp2);
			if(tmp1 == 0)
				break;
			no[tmp1].son.push_back(tmp2);
			no[tmp2].father = tmp1;
		}

		int cur_num = n;
		while(true)
		{
			if (cur_num == 1)
				break;
			double max_v = 0;
			int max_i = 0;
			for (int i = 1; i <= n; ++i)
			{
				//每次找不是根节点的最大权值子集与其父子集合并
				if (no[i].is_setrep && i != r && max_v < no[i].value)
				{
					max_v = no[i].value;
					max_i = i;
				}
			}
			//printf("%d\n", max_i);
			union_node(max_i);

			--cur_num;
		}

		seq[1] = c[r];
		for (int i = 0; i < n - 1; ++i)
		{
			seq[i + 2] = c[no[r].in_set[i]];
		}

		int ans = 0;
		for (int i = 1; i <= n; ++i)
		{
			ans += i*seq[i];
		}
		printf("%d\n", ans);
	}
	return 0;
}



=================
因为没注意到是多组数据,然后wa了一次。


© 著作权归作者所有

locusxt
粉丝 27
博文 140
码字总数 90989
作品 0
海淀
程序员
私信 提问
POJ - 3321 Apple Tree dfs序+线段树 简单题

Apple Tree POJ - 3321 There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully n......

ProLightsfxjh
2017/10/11
0
0
Tree(树链剖分+线段树延迟标记)

Tree http://poj.org/problem?id=3237 Description You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each ......

Fighting_sh
2018/09/25
0
0
poj 1610 Quad Trees

题意 四叉树,就是模拟pr树...不需要建树,直接bfs就行了...因为没注意要输出大写,wa了一遍又一遍→_→..另外提供一小组数据. 1 2 1 1 1 0 答案是154. 输出是大写的16进制....bfs Quad Trees ...

locusxt
2013/12/05
169
0
hduoj题目分类

基础题:1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、1094、1...

hlearning
2014/02/25
0
0
LCT 12 - 02 学习记录

简单讲一讲吧 可以维护一个有根树森林,支持对树的分割, 合并, 对某个点到它的根的路径的某些操作。在我的理解上, 就是动态版的链剖,所以它和链剖一样可以维护子树信息 ,但是十分毒瘤。 ...

aziint
2017/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Centos6.6 安装ffmpeg视频工具

1.安装前置工具 yum -y install gcc cc cl libmpc*//后续失败的话,自己补充自己的缺少的包 2.安装yasm 1)下载wget http://www.tortall.net/projects/yasm/releases/yasm-1.3.0.tar.gz...

小海bug
5分钟前
1
0
电商的支付风控怎么玩?

qwfys
10分钟前
4
0
用什么来做用户行为分析?七个实用工具推荐给你

当企业进入数据化管理阶段之后,就不得不对用户进行行为数据分析,当然其他的包括用户画像、趋势分析等等,都是现在企业经常要进行的营销分析,因此选一个好的数据分析工具是很重要的。 而现...

朕想上头条
11分钟前
1
0
Java mysql连接

import java.sql.DriverManager; import java.sql.SQLException; import com.mysql.jdbc.Connection; public class T { public static void main(String[] args) throws SQLException, Insta......

林词
11分钟前
2
0
Select 选择器 的一些官网没有的用法

一、拼接字符串 <el-option v-for="(item, index) in reagentOptions" :key="index" :label="item.sjlxmc+' '+item.sjbm" :va......

沉迷代码我爱学习
12分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部