http://acm.pku.edu.cn/JudgeOnline/problem?id=2054 http://acm.hdu.edu.cn/showproblem.php?pid=1055
好点经典的一道题目，做了半天都做不出来
后来到网上看了解题报告才明白（解题报告网上有，我就不再出说明了）是n^2的算法
我在想，每次都遍历一遍找最大权值的点会不会太浪费时间，如果用堆取出权值最大的点效率就会有很大改进，变成n*log(n)了
但是最大权值的父亲节点也要从堆中取出，这有点麻烦
结合昨天ZOJ月赛比赛中自创的
可以取出任意节点的二叉堆，记录位子来实现，想到了方法，多方试验之后果然成功了
在PKU提交也只用了16MS...哈哈
贴出来晒晒
#include "stdio.h"
#include "string"
#define maxn 1001
//-----------------------Binary Heap------------------------------------
struct Heap {
int val,cost,time,idx;
}hh[maxn];
int pos[maxn];
int len;
bool Prior(Heap a,Heap b) {
return a.val * b.time > b.val * a.time;
}
void Push(Heap s) {
int i;
for(i = ++len ; i > 1 && Prior(s,hh[i/2]); i /= 2) {
hh[i] = hh[i/2];
pos[hh[i].idx] = i;
}
hh[i] = s;
pos[hh[i].idx] = i;
}
Heap Pop(int idx) {
if(idx == -1) return hh[0];
Heap ret = hh[idx];
Heap last = hh[len--];
int i,s;
for(i = idx ; i * 2 <= len; i = s) {
s = i * 2;
if(s + 1 <= len && Prior(hh[s+1],hh[s])) {
s ++;
}
if(Prior(hh[s],last)) {
hh[i] = hh[s];
pos[hh[i].idx] = i;
} else {
break;
}
}
hh[i] = last;
pos[hh[i].idx] = i;
for(i = idx ; i > 1 && Prior(hh[i],hh[i/2]); i /= 2) {
Heap buf = hh[i];
hh[i] = hh[i/2];
hh[i/2] = buf;
pos[hh[i].idx] = i;
pos[hh[i/2].idx] = i/2;
}
return ret;
}
//---------------------------------------------------------------
int father[maxn];
int main() {
int n,r,i;
hh[0].cost = hh[0].time = hh[0].val = 0;
while(scanf("%d%d",&n,&r),n+r) {
len = 0;
Heap root;
for(i =1 ; i <= n ; i ++) {
Heap buf;
scanf("%d",&buf.cost);
buf.val = buf.cost;
buf.time = 1;
buf.idx = i;
if(i == r) {
root = buf;
} else {
Push(buf);
}
}
for(i = 1 ; i < n ; i ++) {
int a,b;
scanf("%d%d",&a,&b);
father[b] = a;
}
while(len) {
Heap max = Pop(1);
int f = father[max.idx];
if(f == r) {
root.cost += max.cost + max.val * root.time;
root.time += max.time;
root.val += max.val;
} else {
Heap fa = Pop(pos[f]);
fa.cost += max.cost + max.val * fa.time;
fa.time += max.time;
fa.val += max.val;
fa.idx = f;
Push(fa);
}
pos[max.idx] = -1;
}
printf("%d\n",root.cost);
}
return 0;
}
下边是n^2的算法，跑了200+MS。。简洁是简洁，但效率不高
#include "stdio.h"
#include "string"
#define maxn 1001
struct H{
int val;
int cost;
int time;
void clear() {
val = cost = time = 0;
}
}hh[maxn];
int father[maxn];
int main() {
int n,r,i;
while(scanf("%d%d",&n,&r),n+r) {
for(i =1 ; i <= n ; i ++) {
scanf("%d",&hh[i].cost);
hh[i].val = hh[i].cost;
hh[i].time = 1;
}
for(i = 1; i < n ; i ++) {
int a,b;
scanf("%d%d",&a,&b);
father[b] = a;
}
while(true) {
int idx = 0;
for(i = 1 ; i <= n ; i ++) {
if(i != r && hh[i].time && (idx == 0 || hh[idx].val * hh[i].time < hh[i].val * hh[idx].time)) {
idx = i;
}
}
if(idx == 0) break;
int f = father[idx];
hh[f].cost += hh[idx].cost + hh[idx].val * hh[f].time;
hh[f].val += hh[idx].val;
hh[f].time += hh[idx].time;
hh[idx].clear();
}
printf("%d\n",hh[r].cost);
}
return 0;
}
posted on 2009-06-29 16:30
shǎ崽 阅读(1585)
评论(3) 编辑 收藏 引用