记录编号 27198 评测结果 AAAAAAAAAA
题目名称 朦胧之旅 最终得分 100
用户昵称 Gravatar老虎小飞 是否通过 通过
代码语言 Pascal 运行时间 0.022 s
提交时间 2011-08-04 18:08:58 内存使用 0.54 MiB
显示代码纯文本
var
ny,nx,v,x,y,g,d:array[0..10000]of longint;
f:array[0..10000]of boolean;
mo,next:array[0..20000]of longint;
n,m,i,j,t,ty,tx,a,b:longint;

function bfs:boolean;
var a,b,t,h,e,i:longint;
begin
    bfs:=false;
    t:=0;h:=0;
    fillchar(v,sizeof(v),0);
    for i:=1 to tx do begin
        a:=nx[i];
        if x[a]=0 then begin
            inc(t);
            d[t]:=a;
        end;
    end;
    while h<>t do begin
        inc(h);a:=d[h];
        e:=g[a];
        while e<>0 do begin
            b:=mo[e];
            if v[b]=0 then begin
                v[b]:=v[a]+1;
                if y[b]<>0 then begin
                    v[y[b]]:=v[b]+1;
                    inc(t);d[t]:=y[b];
                end
                else bfs:=true;
            end;
            e:=next[e];
        end;
    end;
end;

function dfs(a:longint):boolean;
var b,e:longint;
begin
    dfs:=false;
    e:=g[a];
    while e<>0 do begin
        b:=mo[e];
        if v[b]=v[a]+1 then begin
            v[b]:=0;
            if (y[b]=0)or(dfs(y[b])) then begin
                y[b]:=a;x[a]:=b;exit(true);
            end;
        end;
          e:=next[e];
    end;
end;

begin
assign(input,'lovetravel.in');reset(input);
assign(output,'lovetravel.out');rewrite(output);
    read(n,t,m);
    t:=0;
    for i:=1 to m do begin
        read(a,b,j);
        if not f[a] then begin
            inc(tx);nx[tx]:=a;f[a]:=true;
        end;
        if not f[b] then begin
            inc(ty);ny[ty]:=b;f[b]:=true;
        end;
        inc(t);
        next[t]:=g[a];g[a]:=t;mo[t]:=b;
        inc(t);
        next[t]:=g[b];g[b]:=t;mo[t]:=a;
    end;
    a:=0;
    while bfs do
        for i:=1 to tx do
            if (x[nx[i]]=0)and(dfs(nx[i])) then inc(a);
    writeln('0 ',n-a);
close(input);close(output);
end.