讨论 / 树的最小划分(求优化方法)
zhurui 2010-07-09 23:20:00
点我顶贴 收藏 删除
Program tree;

Const maxn=10000;

Type number=0..300000;

Var

key,s,a:array[1..maxn]of number;

f,g:array[1..maxn]of boolean;

e,son:array[1..maxn,0..300]of number;

n,k,root,w,t:number;

procedure init;

var i,x,y:number;

d:array[1..maxn]of number;

begin

fillchar(d,sizeof(d),0);

readln(n,k,key[1]);

for i:=2 to n do

begin

readln(x,y);

inc(d[x]);inc(e[x,0]);e[x,e[x,0]]:=i;

inc(d[i]);inc(e[i,0]);e[i,e[i,0]]:=x;

key[i]:=y;

end;

for i:=1 to n do

if d[i]=1 then

begin root:=i;break;end;

end;

procedure build(i:number);

var j:number;

begin

f[i]:=true;

for j:=1 to e[i,0] do

if not f[e[i,j]] then

begin

inc(son[i,0]);

son[i,son[i,0]]:=e[i,j];

build(e[i,j]);

end;

end;

function check(i:number):number;

var j,sum:number;

begin

sum:=0;

for j:=1 to son[i,0] do

inc(sum,check(son[i,j]));

inc(sum,key[i]);

if sum>=w then

begin

inc(t); a[t]:=i;

inc(s[i]); sum:=0;

end;

check:=sum;

end;

procedure work1;

var i,sum:number;

begin

sum:=0;for i:=1 to n do inc(sum,key[i]);

w:=sum div (k-1); t:=0;

sum:=check(root);

dec(s[a[t]]);dec(t);

end;

function cal(i:number):number;

var j,sum:number;

begin

sum:=key[i];

for j:=1 to son[i,0] do

if s[son[i,j]]=0 then

inc(sum,cal(son[i,j]));

exit(sum);

end;

procedure work2;

var i,j,w1,w2,temp,l1,l2:number;

begin

for i:=t+1 to k-1 do

begin

inc(s[son[root,1]]);

a[i]:=son[root,1];

end;

while true do

begin

fillchar(g,sizeof(g),false);

w1:=cal(root);

g[root]:=true;

for i:=1 to k-1 do

if g[a[i]] then w1:=0

else begin

temp:=cal(a[i]);

g[a[i]]:=true;

if w1>temp then w1:=temp;

end;

w2:=0;

for i:=1 to k-1 do

for j:=1 to son[a[i],0] do

if s[son[a[i],j]]=0 then

begin

temp:=cal(son[a[i],j]);

if temp>w2 then

begin

w2:=temp;

l1:=i;l2:=j;

end;

end;

if w1<=w2 then

begin

dec(s[a[l1]]);

inc(s[son[a[l1],l2]]);

a[l1]:=son[a[l1],l2];

end

else break;

end;

writeln(w1);

end;

Begin

fillchar(f,sizeof(f),false);

fillchar(e,sizeof(e),0);

fillchar(son,sizeof(son),0);

init;

build(root);

work1;

work2;

End.

查看更多回复
提交回复