sorry about that, but thanks a lot for taking the time to look at my code. : ) the problem ended up being not in my algorithm but in telling whether gophers can make it to holes or not i had a sneaky typo.
[c]
/* find which gophers can make it to which holes */
for (i=0;i<n;i++) for (j=0;j<m;j++) {
if (f >= (gophloc[0]-holesloc[0])*(gophloc[0]-holesloc[0]) +
(gophloc[1]-holesloc[1])*(gophloc[1]-holesloc[1])) c[i+1][n+j+1] = 1;
}
[/c]
instead of the correct
[c]
/* find which gophers can make it to which holes */
for (i=0;i<n;i++) for (j=0;j<m;j++) {
if (f >= (gophloc[0]-holesloc[j][0])*(gophloc[0]-holesloc[j][0]) +
(gophloc[i][1]-holesloc[j][1])*(gophloc[i][1]-holesloc[j][1])) c[i+1][n+j+1] = 1;
}
[/c]
This is my solution. But i got W.A. I used Ford-Fulkerson method to find the maximum bipartite graph matching. I am just studying matching. So if I am wrong with my algorithm please let me know. Thank you
PROGRAM Gopher2_10080;
const source=401; target=402;
var
c:array [0..402,0..402] of 0..1;
x,y,x1,y1:array [0..400] of double;
ans,i,n,m,s,v:integer;
function dis(x1,y1,x2,y2:double):double;
var k1,k2:real;
begin
k1:=sqr(x2-x1);
k2:=sqr(y2-y1);
dis:=sqrt(k1+k2)
end;
procedure init;
var i,j:integer;
k:real;
begin
for i:=1 to n do
for j:=n+1 to m+n do
begin
k:=dis(x,y,x1[j],y1[j]);
if k<=s*v then c[i,j]:=1;
end;
for i:=1 to n do
c[source,i]:=1;
for i:=n+1 to n+m do
c[i,target]:=1;
end;
procedure solve;
var i,j:integer;
begin
for i:=1 to n do
for j:=n+1 to m+n do
if c[source,i]=1 then
if c[i,j]=1 then
if c[j,target]=1 then
begin
c[source,i]:=0;
c[i,j]:=0;
c[j,target]:=0;
inc(ans);
end;
end;
begin
while not eof(input) do
begin
ans:=0;
fillchar(c,sizeof(c),0);
readln(input,n,m,s,v);
for i:=1 to n do
readln(input,x,y);
for i:=1 to m do
readln(input,x1[i+n],y1[i+n]);
init;
solve;
ans:=n-ans;
writeln(output,ans:1);
end;
end.
I had the exact same output.
Actually, the output is:
0
0
I got ACC after changing a line which said something like this:
link[E[now]] = i;
into:
line[E[now]] = now;
Maybe you made the same mistake ( because you have the same output )
( link is an int array which says that the gopher link[x] is going to the hole x, and E is an adjency list of holes that are reachable for gopher now )
There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=2954)
forum 'Volume C' description wrote:All about problems in Volume C. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
[/u]