| ||||||||||
| 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