随笔-72  评论-126  文章-0  trackbacks-0
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ǎ崽 阅读(1523) 评论(3)  编辑 收藏 引用

评论:
# re: hdu1055 & PKU2054------DP+可以任意取出节点的二叉堆 2009-06-30 11:10 | hhanger
可以取出任意节点的二叉堆

这个好像叫映射二叉堆。

这个是不是可以直接用set来实现呢?  回复  更多评论
  
# re: hdu1055 & PKU2054------DP+可以任意取出节点的二叉堆 2009-06-30 11:12 | hhanger
发现变量名是hh,哈哈~~  回复  更多评论
  
# re: hdu1055 & PKU2054------DP+可以任意取出节点的二叉堆 2009-07-02 13:04 | shǎ崽
@hhanger
哦,“映射二叉堆”原来已经有名字了的,哎呀,我孤陋寡闻了。。

呵呵,我习惯把一些数组名都取做hh的,哈哈~~  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理