Guest User

Untitled

a guest
May 20th, 2010
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/perl                                                          
  2. # coded by Sergei Kirjanov                                                
  3. # with advice from the team :)                                            
  4. use strict;                                                              
  5. my %w;   # $w{node_name} is node_weight                                  
  6. my %p;   # $p{node_name} is node_parent_name                              
  7. my %h;   # for heavy $h{branch_root_name} is branch_weight                
  8. my %l;   # for light $l{branch_root_name} is branch_weight                
  9. my %has; # $has{branch_root_name}{node_name} is 1 if node is in branch    
  10. my @res; # branch_root cutting seq                                        
  11.                                                                          
  12. my($bs,@in) = <STDIN>;                                                    
  13. $bs=~/^buffer\=(\d+)/ and $bs=$1 or die $bs;                              
  14. # parsing node info:                                                      
  15. /(\w),(\d+),((\w)|\-)/ and ($w{$1},$p{$1})=($2,$4) or die "{$_}" for @in;
  16. # precalculating for branches (branch for every node)                    
  17. for(keys %p){                                                            
  18.     for(my $c=$_;$c;$c=$p{$c}){                                          
  19.         $h{$c} += $w{$_};                                                
  20.         $has{$c}{$_} = 1;                                                
  21.     }                                                                    
  22. }                                                                        
  23. $h{$_}<=$bs and $l{$_} = delete $h{$_} for keys %h;                      
  24. # cut optimal branches from tree, one by one                              
  25. # I can not proove this will be truely the optimal method                
  26. while(1){                                                                
  27.     my($n,$w); # chosen node_name and weight                              
  28.     # choose heaviest of light branches                                  
  29.     # %l should be replaced by some autosorting structure for big trees  
  30.     $l{$_}>$w and ($n,$w)=($_,$l{$_}) and $w==$bs and last for keys %l;  
  31.     push @res, $n||last;                                                  
  32.     delete @l{keys %{$has{$n}}}; # remove branch nodes                    
  33.     # reduce weights of parents                                          
  34.     $h{$n}-=$w, $h{$n}<=$bs and $l{$n} = delete $h{$n} while $n=$p{$n};  
  35. }                                                                        
  36. print @res, %h ? " - stop\n":" - ok\n";
RAW Paste Data