测评机: Xeost[5]
得分: 80分
提交日期: 2009-1-18 11:16:00
有效耗时: 2016毫秒
测试结果1: 通过本测试点|有效耗时437:ms
测试结果2: 通过本测试点|有效耗时172:ms
测试结果3: 通过本测试点|有效耗时250:ms
测试结果4: 通过本测试点|有效耗时172:ms
测试结果5: 通过本测试点|有效耗时359:ms
测试结果6: 通过本测试点|有效耗时250:ms
测试结果7: 通过本测试点|有效耗时313:ms
测试结果8: 选手程序运行超过时限
测试结果9: 测试结果错误.错误结果为:348
正确结果应为:344
测试结果10: 通过本测试点|有效耗时63:ms
================华丽的分割线===========
状态: Accepted
测评机: Xeost[5]
得分: 100分
提交日期: 2009-1-18 19:30:00
有效耗时: 2360毫秒
测试结果1: 通过本测试点|有效耗时266:ms
测试结果2: 通过本测试点|有效耗时172:ms
测试结果3: 通过本测试点|有效耗时219:ms
测试结果4: 通过本测试点|有效耗时156:ms
测试结果5: 通过本测试点|有效耗时250:ms
测试结果6: 通过本测试点|有效耗时219:ms
测试结果7: 通过本测试点|有效耗时250:ms
测试结果8: 通过本测试点|有效耗时547:ms
测试结果9: 通过本测试点|有效耗时219:ms
测试结果10: 通过本测试点|有效耗时62:ms
大家注意
匈牙利要用BFS实现
铁的事实证明BFS的时效要比DFS快
program Hopcroft;
const
maxn = 2000;
type
link = ^obj1;
obj1 = record
v: longint;
next: link;
end;
var
head, tail: array [1..2, 1..maxn] of link;
dist, match: array [1..2, 1..maxn] of longint;
r, check: array [1..maxn] of boolean;
q: array [1..maxn] of longint;
len, n, m, i, j, x: longint;
function search(x: longint): boolean;
var
work: link;
t1, t2, k: longint;
begin
if dist[1, x] > len then
exit(false);
work := head[1, x];
while work <> nil do
begin
k := work^.v;
if (not check[k]) and (dist[2, k] = dist[1, x] + 1) then
begin
check[k] := true;
t1 := match[1, x];
t2 := match[2, k];
match[1, x] := k;
match[2, k] := x;
if (t2 = 0) or search(t2) then
exit(true);
match[1, x] := t1;
match[2, k] := t2
end;
work := work^.next
end;
exit(false)
end;
procedure init;
var
i: longint;
begin
for i := 1 to n do
begin
head[1, i] := nil;
head[2, i] := nil;
tail[1, i] := nil;
tail[2, i] := nil
end
end;
procedure addEdge(x, y: longint);
var
work: link;
begin
new(work);
work^.next := nil;
work^.v := y;
if head[1, x] = nil then
begin
head[1, x] := work;
tail[1, x] := work
end
else
begin
tail[1, x]^.next := work;
tail[1, x] := work
end;
new(work);
work^.next := nil;
work^.v := x;
if head[2, y] = nil then
begin
head[2, y] := work;
tail[2, y] := work
end
else
begin
tail[2, y]^.next := work;
tail[2, y] := work
end
end;
function maxMatch: longint;
var
qs, qe, i, k, s: longint;
work: link;
begin
fillchar(match, sizeof(match), 0);
repeat
fillchar(dist, sizeof(dist), 0);
qs := 1;
qe := 0;
for i := 1 to n do
if match[1, i] = 0 then
begin
inc(qe);
q[qe] := i;
dist[1, i] := 1
end;
len := maxlongint;
while qs <= qe do
begin
work := head[1, q[qs]];
while work <> nil do
begin
k := work^.v;
if dist[2, k] = 0 then
begin
dist[2, k] := dist[1, q[qs]] + 1;
if match[2, k] <> 0 then
begin
inc(qe);
q[qe] := match[2, k];
dist[1, match[2, k]] := dist[2, k] + 1
end
else
if dist[2, k] < len then
len := dist[2, k]
end;
work := work^.next
end;
inc(qs)
end;
if len = maxlongint then
break;
fillchar(check, sizeof(check), false);
for i := 1 to n do
if match[1, i] = 0 then
search(i);
until false;
s := 0;
for i := 1 to n do
inc(s, ord(match[1, i] <> 0));
maxMatch := s
end;
begin
readln(n);
init;
for i := 1 to n do
begin
read(m);
fillchar(r, sizeof(r), 0);
for j := 1 to m do
begin
read(x);
r[x] := true
end;
for j := 1 to n do
if not r[j] then
addEdge(i, j)
end;
writeln(maxMatch)
end.