讨论 / 超时的人请注意
~★熊¤熊★~ 2009-01-25 11:49:00
点我顶贴 收藏 删除
状态: Unaccepted

测评机: 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快

#1 cloudygoose@2009-01-23 21:22:00
回复 删除
可以不用BFS,只需要在匈牙利DFS时用邻接表(而不是邻接矩阵)枚举就可以AC!
#2 wish@2009-01-25 11:49:00
回复 删除
事实证明 Hopcroft 仍然无视一切。。。。。

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.

查看更多回复
提交回复