记录编号 |
27198 |
评测结果 |
AAAAAAAAAA |
题目名称 |
朦胧之旅 |
最终得分 |
100 |
用户昵称 |
老虎小飞 |
是否通过 |
通过 |
代码语言 |
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.