Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

诡异的初始化

Posted by The_Dawn at 2011-06-22 23:27:05 on Problem 1848
改变初始化的方式就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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator