讨论 / 匈牙利算法竟然超时?!
wxfred 2008-08-28 01:50:00
点我顶贴 收藏 删除
状态: Unaccepted

测评机: Virmain[1]

得分: 90分

有效耗时: 177毫秒

测试结果1: 测试结果正确

测试结果2: 测试结果正确

测试结果3: 测试结果正确

测试结果4: 测试结果正确

测试结果5: 测试结果正确

测试结果6: 测试结果正确

测试结果7: 测试结果正确

测试结果8: 无输出|运行超时

测试结果9: 测试结果正确

测试结果10: 测试结果正确

我的程序:

program pp;

var

b:array[1..1000] of boolean;

f:array[1..1000,1..1000] of boolean;

d:array[1..1000] of integer;

n,all:integer;

procedure init;

var

i,j,m,p:integer;

begin

read(n);

for i:=1 to n do

begin

read(m);

for j:=1 to m do

begin

read(p);

f[i,p]:=true;

end;

end;

if n=0 then

begin

write(0);

halt;

end;

end;

function find(p:integer):boolean;

var

i:integer;

begin

for i:=1 to n do if (not f[p,i])and(not b[i]) then

begin

b[i]:=true;

if (d[i]=0)or(find(d[i])) then

begin

d[i]:=p;

exit(true);

end;

end;

exit(false);

end;

procedure main;

var

i:integer;

begin

for i:=1 to n do

begin

fillchar(b,sizeof(b),false);

if find(i) then inc(all);;

end;

write(all);

end;

begin

init;

main;

end.

难道我编错了?

请大牛帮忙指出,谢谢.

#1 fjxmlhx@2008-06-04 05:43:00
回复 删除
Dinic。。。

增加一个超级源S,使S与X集里所有顶点相连,容量为1. 增加一个超级辉T,使T与Y集里所有顶点相连,容量为1.若X集与Y集的某些顶点有相连,那么容量为1.这时候,一个网络的模型就展现在我们的眼前.接下来最大流算法即可.

#2 wxfred@2008-06-04 06:22:00
回复 删除
我知道DINIC,谢谢.

但我想知道,匈牙利不行吗?

有人在该题讨论说可以呀.

#3 wish@2008-06-04 06:51:00
回复 删除
Hopcroft Algorithm 王道………………

#4 平大爷的马甲@2008-06-08 23:33:00
回复 删除
我也是用匈牙利算法,和你一样出错.我也郁闷

照理说在时间复杂度上是可以过得.

用最大流也不过是差不多的时间复杂度

#5 fjxmlhx@2008-06-11 04:13:00
回复 删除
N^0.5M

最大流算法不是差一点~!

#6 sqybi@2008-06-19 23:32:00
回复 删除
Hopcroft也TLE 靠
#7 little@2008-08-05 05:26:00
回复 删除
只能够说这是RP的问题,我直接用记事本写个标准的匈牙利算法然后没编译就交上去了..然后便AC...
#8 DarkMaster@2008-08-27 23:57:00
回复 删除
最大流的重标记与前移算法~~
#9 Zx.MYS@2008-08-28 01:50:00
回复 删除
我用匈牙利算法就AC了……
查看更多回复
提交回复