Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
诡异的初始化改变初始化的方式就AC。附2次代码,望神牛指出错误所在。 这个是第一次寻找叶子,用判断节点是否是叶子进行初始化。WA。 const INF=10000; var n,i,j,k,x,y:longint; b:array[0..101,0..101]of longint; v,leaf:array[0..101]of boolean; f:array[0..101,0..2]of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure init; begin read(n); for i:=1 to n-1 do begin read(x,y); inc(b[x,0]);b[x,b[x,0]]:=y; inc(b[y,0]);b[y,b[y,0]]:=x; end; filldword(f,sizeof(f)shr 2,INF); end; procedure findleaf(w:longint); var i,j:longint; begin v[w]:=true;leaf[w]:=true; for i:=1 to b[w,0] do begin if v[b[w,i]] then continue; leaf[w]:=false; findleaf(b[w,i]); end; end; procedure treedp(w:longint); var i,j,fa,sum:longint; begin v[w]:=true; if leaf[w] then begin f[w,1]:=0; exit; end; for i:=1 to b[w,0] do if v[b[w,i]] then fa:=b[w,i] else treedp(b[w,i]); sum:=0; for i:=1 to b[w,0] do if b[w,i]<>fa then inc(sum,f[b[w,i],0]); if sum<INF then f[w,1]:=sum else f[w,1]:=INF; for i:=1 to b[w,0] do begin if b[w,i]=fa then continue; f[w,2]:=min(f[w,2],sum-f[b[w,i],0]+min(f[b[w,i],1],f[b[w,i],2])); end; for i:=1 to b[w,0] do begin if b[w,i]=fa then continue; f[w,0]:=min(f[w,0],sum-f[b[w,i],0]+f[b[w,i],2]+1); end; for i:=1 to b[w,0] do for j:=i+1 to b[w,0] do if (b[w,i]<>fa) and (b[w,j]<>fa) then f[w,0]:=min(f[w,0],sum-f[b[w,i],0]-f[b[w,j],0]+min(f[b[w,i],1],f[b[w,i],2])+min(f[b[w,j],1],f[b[w,j],2])+1); end; begin init; findleaf(1); fillchar(v,sizeof(v),0); treedp(1); if f[1,0]>=INF then writeln(-1) else writeln(f[1,0]); end. ———————————————————————————————————— 这个是第二次。直接filldword初始化。AC。 const INF=10000; var n,i,j,k,x,y:longint; b:array[0..101,0..101]of longint; v:array[0..101]of boolean; f:array[0..101,0..2]of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure init; begin read(n); for i:=1 to n-1 do begin read(x,y); inc(b[x,0]);b[x,b[x,0]]:=y; inc(b[y,0]);b[y,b[y,0]]:=x; end; filldword(f,sizeof(f)shr 2,INF); end; procedure treedp(w:longint); var i,j,fa,sum:longint; begin v[w]:=true; for i:=1 to b[w,0] do if v[b[w,i]] then fa:=b[w,i] else treedp(b[w,i]); sum:=0; for i:=1 to b[w,0] do if b[w,i]<>fa then inc(sum,f[b[w,i],0]); if sum<f[w,1] then f[w,1]:=sum; for i:=1 to b[w,0] do begin if b[w,i]=fa then continue; f[w,2]:=min(f[w,2],sum-f[b[w,i],0]+min(f[b[w,i],1],f[b[w,i],2])); end; for i:=1 to b[w,0] do begin if b[w,i]=fa then continue; f[w,0]:=min(f[w,0],sum-f[b[w,i],0]+f[b[w,i],2]+1); end; for i:=1 to b[w,0] do for j:=i+1 to b[w,0] do if (b[w,i]<>fa) and (b[w,j]<>fa) then f[w,0]:=min(f[w,0],sum-f[b[w,i],0]-f[b[w,j],0]+min(f[b[w,i],1],f[b[w,i],2])+min(f[b[w,j],1],f[b[w,j],2])+1); end; begin init; treedp(1); if f[1,0]>=INF then writeln(-1) else writeln(f[1,0]); end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator