比赛 |
20101101 |
评测结果 |
WWWWWWWWWW |
题目名称 |
树的最大匹配 |
最终得分 |
0 |
用户昵称 |
亟隐 |
运行时间 |
0.004 s |
代码语言 |
Pascal |
内存使用 |
0.21 MiB |
提交时间 |
2012-11-05 11:58:22 |
显示代码纯文本
type nodd=record
y,n:longint;
end;
var f,g:array[0..1000,0..2]of longint;
a,d:array[0..1000]of longint;
b:array[0..2000]of nodd;
n,i,x,m,y,t,j:longint;
sum,xx:int64;
procedure add(x,y:longint);
begin
inc(t); b[t].y:=y;
b[t].n:=a[x]; a[x]:=t;
end;
procedure init;
begin
readln(n); t:=0;
sum:=0; xx:=1;
for i:=1 to n do
begin
read(x,m);
for j:=1 to m do
begin
read(y); add(x,y); inc(d[y]);
end;
end;
end;
procedure dfs(t:longint);
var p,y:longint;
begin
g[t,2]:=1; g[t,0]:=1;
f[t,1]:=0; g[t,1]:=1;
p:=a[t];
while p<>0 do
begin
y:=b[p].y; dfs(y);
if f[y,0]>0 then begin f[t,2]:=f[t,2]+f[y,0]; g[t,2]:=1; end
else if f[y,0]=0 then g[t,2]:=g[t,2]*g[y,0];
f[t,1]:=f[t,1]+f[y,2]; g[t,1]:=g[t,1]*g[y,2];
if f[y,1]>0then
begin
f[t,1]:=f[y,1]+f[t,1]; g[t,1]:=1;
end else if f[y,1]=0 then g[t,1]:=g[t,1]+1;
if f[y,0]>0then
begin
f[t,1]:=f[y,0]+f[t,1]; g[t,1]:=1;
end else if f[y,0]=0 then g[t,1]:=g[t,1]+1;
if f[y,2]+1+f[t,0]>f[t,1] then
begin
f[t,1]:=f[y,2]+1+f[t,0]; g[t,1]:=1;
end else if f[y,2]+1+f[t,0]=f[t,1] then g[t,1]:=g[t,1]+1;
if f[y,1]>f[y,0] then
begin
f[t,0]:=f[t,0]+f[y,1];
g[t,0]:=g[t,0]*g[y,1];
end else if f[y,1]<f[y,0] then
begin
f[t,0]:=f[t,0]+f[y,0];
g[t,0]:=g[t,0]*g[y,0];
end else
begin
f[t,0]:=f[t,0]+f[y,1];
g[t,0]:=g[t,0]*(g[y,1]+g[y,0]);
end;
p:=b[p].n;
end;
end;
procedure work;
begin
for i:=1 to n do if d[i]=0 then
begin
dfs(i);
if (f[i,0]>f[i,1]) then
begin
sum:=sum+f[i,0];
xx:=xx*g[i,0];
end else if f[i,0]<f[i,1] then
begin
sum:=sum+f[i,1];
xx:=xx*g[i,0];
end else
begin
sum:=sum+f[i,0];
xx:=xx*(g[i,0]+g[i,1]);
end;
end;
writeln(sum);
writeln(xx);
end;
begin
assign(input,'treeb.in');reset(input);
assign(output,'treeb.out');rewrite(output);
init;
work;
close(input); close(output);
end.