记录编号	20974	评测结果	WWWWWWWWWW
题目名称	489.树的最大匹配	最终得分	0
用户昵称	belong.zmx	是否通过	未通过
代码语言	Pascal	运行时间	0.003 s
提交时间	2010-11-02 09:02:50	内存使用	1.08 MiB

program treeb(input,output);
var
 m,n,root:longint;
 flag:boolean;
 a:Array[1..1000,1..1000]of boolean;
 f:array[0..1000,1..4]of longint;
 x,y,i,j:longint;

function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;

procedure dp(x:longint);
var
 i,j:longint;
 zz,cc:longint;
 flag:boolean;
 gg:longint;
begin
 zz:=maxlongint;
 flag:=false;
 cc:=0;
 for i:=1 to n do
 begin
  if a[i,x]=true then
  begin
   dp(i);
   flag:=true;
   if abs(f[i,2]-f[i,1])<zz then
   begin
    zz:=abs(f[i,2]-f[i,1]);
    cc:=i;
   end
  end;
 end;
 if flag=true then
 begin
 for i:=1 to n do
  if (a[i,x]=true) then
  begin
   if i<>cc then
    f[x,1]:=f[x,1]+max(f[i,2],f[i,1])
   else
    f[x,1]:=f[x,1]+f[i,2]+1;
   f[x,2]:=f[x,2]+max(f[i,1],f[i,2]);
  end;
 end;
end;

begin
 assign(input,'treeb.in');
 reset(input);
 readln(n);
 for i:=1 to n do
 begin
  read(x);
  read(m);
  for j:=1 to m do
  begin
   read(y);
   a[y,x]:=true;
  end;
 end;
 close(input);

 for i:=1 to n do
 begin
  f[i,3]:=1;
  f[i,4]:=1;
 end;

 for i:=1 to n do
 begin
  flag:=true;
  for j:=1 to n do
   if a[i,j]=true then
   begin
    flag:=false;
    break;
   end;
  if flag=true then
  begin
   root:=i;
   break;
  end;
 end;

 dp(root);

 assign(output,'treeb.out');
 rewrite(output);
 writeln(max(f[root,1],f[root,2]));
 close(output);
end.