|
|
back to boardAfter 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. Posted by Saturn 10 Jul 2004 20:42 Can you help me in this prolem I got WA many times HINT Posted by etam 10 Jul 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 Posted by Saturn 10 Jul 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. Posted by Saturn 11 Jul 2004 16:34 Re: HINT Posted by bug27 18 Mar 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. |
|
|
