现在的位置: 首页 > 综合 > 正文

Pku2054 Color a Tree(并查集优化+堆优化+贪心)

2017年10月12日 ⁄ 综合 ⁄ 共 1942字 ⁄ 字号 评论关闭

原题 http://poj.org/problem?id=2054

题目大意:给你一棵树及每个点的权值和根,你需要把这颗树染色,每个时间只能染一个点(染一个点必须先染他的父亲),所需的花费是当前染色时间*这个点的权值,求最少花费(根必须第一个染),n<=1000  都组数据

这题初看时以为是tree dp ,但没有想出来,还是看了题解,发现是贪心,但是讲的都不明觉厉,只好拿着代码自己想了。。。。

这个题的大体思路就是最大一个要最先选,但是选它必须要选它父亲。于是我们就可以找到一个点X它的V[X]/num[X]是整棵树中最大的(用过的不算,root也不算),num[X]代表X号点所在的点是由几个点合并而成的,至于为什么是V[X]/num[X],就是求一个v[X]的平均值。设Y是他的父亲,那么就可以把X与Y合并成Y(合并之后X的儿子的父亲就是Y了),我们记V[i]表示i号点的权值,一个点的的花费就是从它祖先的num之和*它的权值,那么在合并X、Y时,就把ans加上num[Y]*V[X],然后把V[Y]增加V[X]就可以把以后祖先的num*v[X]也算进去了,当然num[Y]也要加上num[X],因为X的儿子的父亲从X变成了Y。如此合并
n-1次后,就只剩一个跟节点了,这时再把ans加上V[root]就行了(第一个要染的点事root,所以每个点的染色时间都要+1,ans就应该加上给你的权值的和)

这题裸的是O(n^2)虽说可以过,不过可以用堆+并查集思想优化到(nlogn)

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#define maxn 5100
using namespace std;
struct zy{
	int no,v,sum;
	zy(){}
	zy(int no,int v,int sum):no(no),v(v),sum(sum){}
	bool operator <(const zy&xx)const{return v*xx.sum<xx.v*sum;}
};
inline int read(){
	int tmp=0;char ch;
	while(ch=getchar())if('0'<=ch&&ch<='9')break;
	for(;'0'<=ch&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';
	return tmp;
}
priority_queue<zy>tre;
int sum[maxn],now[maxn],pre[maxn],son[maxn],tot,fa[maxn],rt,val[maxn],n;
bool bb[maxn];
void con(int a,int b){
	pre[++tot]=now[a];
	now[a]=tot;
	son[tot]=b;
}
int findmax(int rt){
	while(bb[tre.top().no]||tre.top().no==rt)tre.pop();
	return tre.top().no;
}
int find(int x){
	if(bb[fa[x]])fa[x]=find(fa[x]);
	return fa[x];
}
inline void Union(int a,int b){  
    val[b]+=val[a];  
    sum[b]+=sum[a];  
    for (int p=now[a];p;p=pre[p]) 
        fa[son[p]]=b;  
}  
void work(){
	int ans=0;
	for(int i=1;i<n;i++){
		int tmp=findmax(rt);
		bb[tmp]=1;
		int faa=find(tmp);
		ans+=val[tmp]*sum[faa];
		Union(tmp,faa);
		tre.push(zy(faa,val[faa],sum[faa]));
	}
	ans+=val[rt];
	printf("%d\n",ans);
}
int main(){
	while(n=read(),rt=read(),n+rt){
		memset(now,0,sizeof(now));
		memset(bb,0,sizeof(bb));
		tot=0;
		while(!tre.empty())tre.pop();
		for(int i=1;i<=n;i++){
			val[i]=read();sum[i]=1;
			tre.push(zy(i,val[i],1));
		}
		for(int i=1;i<n;i++){int a=read(),b=read();con(a,b);fa[b]=a;}
		work();
	}
//	system("pause");
}

【上篇】
【下篇】

抱歉!评论已关闭.