http://acm.pku.edu.cn/JudgeOnline/problem?id=2054 http://acm.hdu.edu.cn/showproblem.php?pid=1055
好點(diǎn)經(jīng)典的一道題目，做了半天都做不出來(lái)
后來(lái)到網(wǎng)上看了解題報(bào)告才明白（解題報(bào)告網(wǎng)上有，我就不再出說(shuō)明了）是n^2的算法
我在想，每次都遍歷一遍找最大權(quán)值的點(diǎn)會(huì)不會(huì)太浪費(fèi)時(shí)間，如果用堆取出權(quán)值最大的點(diǎn)效率就會(huì)有很大改進(jìn)，變成n*log(n)了
但是最大權(quán)值的父親節(jié)點(diǎn)也要從堆中取出，這有點(diǎn)麻煩
結(jié)合昨天ZOJ月賽比賽中自創(chuàng)的
可以取出任意節(jié)點(diǎn)的二叉堆，記錄位子來(lái)實(shí)現(xiàn)，想到了方法，多方試驗(yàn)之后果然成功了
在PKU提交也只用了16MS...哈哈
貼出來(lái)曬曬
#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。。簡(jiǎn)潔是簡(jiǎn)潔，但效率不高
#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ǎ崽 閱讀(1637)
評(píng)論(3) 編輯 收藏 引用