讨论 / 这题大家是怎么存储的啊?
guoshi3 2011-07-26 01:52:00
点我顶贴 收藏 删除
用树?用图?我觉得好像用图(邻接表)方便些。如果用树是怎么建的树啊
#1 lizhixin@2008-10-09 06:58:00
回复 删除
邻接表,在题解里有我的程序

#2 ricky_5@2008-11-05 19:05:00
回复 删除
const maxn=1000;

var n,m,i,x,y,t:longint;

v:array[1..maxn] of longint;

a:array[0..maxn,0..maxn] of longint;

fa:array[0..maxn] of longint;

f:array[0..maxn,0..1] of longint;

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

function dp(node,x:longint):longint;

var s,ii,s1,s0:longint;

begin

if g[node,x] then begin dp:=f[node,x]; exit; end;

if x=1 then begin

s:=v[node];

for ii:=1 to a[node,0] do

s:=s+dp(a[node,ii],0);

f[node,1]:=s; dp:=s; g[node,1]:=true;

end;

if x=0 then begin

s:=0;

for ii:=1 to a[node,0] do begin

s0:=dp(a[node,ii],0);

s1:=dp(a[node,ii],1);

if s0>s1 then s:=s+s0 else s:=s+s1;

end;

f[node,0]:=s; dp:=s; g[node,0]:=true;

end;

end;

begin

read(n,m);

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

for i:=1 to n do read(v[i]);

for i:=1 to m do begin

read(x,y);

if fa[x]<>0 then begin t:=x; x:=y; y:=t; end;

fa[x]:=y; a[y,0]:=a[y,0]+1; a[y,a[y,0]]:=x;

end;

for i:=1 to n do

if fa[i]=0 then begin

a[0,0]:=a[0,0]+1;

a[0,a[0,0]]:=i;

end;

t:=dp(0,0);

writeln(t);

end.

#3 xiaokeke@2008-11-05 23:59:00
回复 删除
支持 临接表
#4 wjltz@2011-07-26 01:52:00
回复 删除
丑陋的使用了邻接矩阵……
查看更多回复
提交回复