比赛 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.