|
|
вернуться в форумAfter mending the MLE I'm getting TLE(#7). How to speed up? program ural1109;
const
maxn=1000;
var
g:array[1..maxn,1..maxn div 8]of byte;
link:array[1..maxn]of integer;
x,y:array[1..maxn]of boolean;
m,n,k,i,s,t:integer;
procedure setedge(x,y:integer);
var
a,b:byte;
begin
a:=(y-1) shr 3+1;
b:=(y-1) mod 8;
g[x,a]:=g[x,a] or (1 shl b);
end;
function adj(x,y:integer):boolean;
var
a,b:byte;
begin
a:=(y-1) shr 3+1;
b:=(y-1) mod 8;
adj:=odd(g[x,a] shr b);
end;
function find(v:integer):boolean;
var
i:integer;
begin
x[v]:=true;
for i:=1 to n do
if adj(v,i) and not y[i] then begin
y[i]:=true;
if (link[i]=0) or find(link[i]) then begin
find:=true;link[i]:=v;exit;
end;
end;
find:=false;
end;
begin
readln(m,n,k);
for i:=1 to k do begin
readln(s,t);
setedge(s,t);
end;
fillchar(link,sizeof(link),0);
t:=m+n;
for i:=1 to m do begin
fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
if find(i) then dec(t);
end;
writeln(t);
end. AC now. Really tricky -- it's the order of searching. Re: AC now. Really tricky -- it's the order of searching. Послано Saturn 10 июл 2004 20:42 Can you help me in this prolem I got WA many times HINT Послано etam 10 июл 2004 21:41 Don't start with an empty matching. Init it using some greedy technique.
My AC: time:0.093, mem:1205 Re: HINT Послано Saturn 10 июл 2004 23:19 When searching for an augpath try unmatched Y vertices first. A matched Y vertex will lead the prog to recurse, thus making it slow. Re: When searching for an augpath try unmatched Y vertices first. A matched Y vertex will lead the prog to recurse, thus making it slow. Послано Saturn 11 июл 2004 16:34 Re: HINT Послано bug27 18 мар 2005 21:45 This method works fantastic!
my AC time is just 0.031s Thanks a lot! 0.031 s 217 KB I wanna thank all those skillful problem solvers on this webboard, whoose pieces of advice helped me to solve this problem. I combined all my skills and knowledge to improve my solution and got AC in 0.031 s, consuming only 217 KB out of 1350 KB provided! This is a wonderful problem, I think...
Well... Frankly, this is my first successfully solved problem on bipartite graphs matching... As easy as that! That's why I'm so excited!
Thank you muchly! Once again! And... Please, forgive me my poor English. |
|
|
