## 10080 - Gopher II

Moderator: Board moderators

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
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]

[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]

53460MF
New poster
Posts: 5
Joined: Wed Jun 29, 2005 7:29 am

### GOT W.A plz help me

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);
for i:=1 to n do
for i:=1 to m do
init;
solve;
ans:=n-ans;
writeln(output,ans:1);
end;
end.

53460MF
New poster
Posts: 5
Joined: Wed Jun 29, 2005 7:29 am
I checked the tests above and i got correct. But I got WA from the Online Judge.

jaywinyeah
New poster
Posts: 19
Joined: Sun Aug 17, 2003 10:40 pm
I have been getting WA and could use some test cases that help me debug my code. What should be the output for this:

76 93 23 8
737.8724003868243 318.3671073461939
807.7005524303653 616.132715881538
244.58125764410897 922.0838058729886
479.35074556549574 799.422385935254
581.4330401775208 890.4530246092941
834.1286527375951 847.8367031294762
172.91064772253594 274.7433191421682
181.686404582872 236.89660110956757
526.679059723186 124.87227558561575
658.9414187811768 16.19941829548477
835.5138515689121 316.3651024720065
262.4748519667337 838.9003933016363
732.8408808861531 751.1165256371288
66.2948527724041 988.1813547215023
19.54467116063052 989.1150936834181
954.8290192717897 489.60462308171384
274.4293265417721 814.5787815298722
561.3620530825242 735.1636125562244
136.69298485182924 717.488777395392
743.7365140964102 913.0061016991324
706.0024416009121 780.2989501573148
851.9854880042926 936.2201905919617
944.2321132647716 999.635893024724
246.66825277035366 494.7364720996932
182.65743654065548 644.0946012323406
12.031017575168445 316.3149439474374
839.3694463391146 851.773712879608
574.7167436635547 715.7484425144105
233.9041769602236 304.9829705003656
986.5995551939989 35.82874961674254
949.5565855553965 484.5948021023695
959.4204586028566 639.2857435169233
538.5759162475598 702.8011974257017
349.25326286612903 697.8236922286612
491.41508026042567 840.5757421860409
680.4305547949151 142.5430341605628
298.4342089636706 474.93009629619365
471.4117322245296 789.4502665220031
120.93428778238314 871.0929160845717
579.1759749602184 834.4219567290363
58.12370948073264 136.0285366546311
514.0752314263951 623.9039096922543
247.59733940577433 682.2517546849908
693.6835382537416 850.7896476681005
69.13347310610118 34.684037475769536
902.0305669303506 99.33707618202303
535.0917195423008 928.3355203095708
799.7088932149895 968.6460010897337
545.4206206904181 590.8863753259768
190.69621557062743 841.1331606200077
61.260358211399854 81.78003446689152
893.3348633665562 730.6057614481821
408.35318511763154 568.2299822876921
485.762968837341 543.9483697222562
859.9498708263928 458.58056708088566
900.1932280673099 521.1019429450646
368.62773990480724 384.7517923246869
825.786007171752 579.9282139388952
817.4119720598619 128.03691443715059
146.46640218410812 785.7165256030409
442.81859105663676 716.3103640243753
187.88505596757577 189.50411616306562
145.91430290342223 85.74341206683478
376.8251093422136 835.0450373239373
252.21442297516862 896.4130203495495
26.708712450577043 821.1772478695033
907.2171521809273 318.72952982777014
354.45826644915667 924.5008750132884
701.5989187993458 866.3967364782436
506.8190363339693 436.6952315605289
308.5718720460197 641.6578326560624
328.35147972602 551.4659964389264
885.6313428324223 679.8694791111958
838.6529628084314 848.0281120817289
743.897759295705 432.9851256111651
902.970377391471 161.1939178619678
320.4836128824256 815.3179592936095
378.21653390671605 402.5501074030252
802.7933435918966 649.993291016167
95.50481415406942 702.8714926456346
848.3898427231542 800.788107249916
400.6682609325024 582.8329081280611
720.0383254313846 751.5961802087006
615.8305079343019 727.2455772436119
812.7648005444915 904.5446559613302
707.9480386765591 337.4572970979232
988.2425892439151 407.82831519556385
654.3441812247723 967.2209182123512
351.5474796663638 895.6158514122571
480.60755903142325 209.2488509015471
106.29830349083558 124.92223211303832
712.8284173327162 592.8355082100494
906.4260113182842 128.1298177963769
33.99872668404813 577.3444276035995
686.2917194085064 164.88033354470565
263.502639189389 582.0194987575544
295.6000040001027 453.34849875091453
388.9762256632994 579.495284458572
391.53040459745426 388.4476122121685
271.4163092117916 898.5442231977332
947.7370831182882 713.3057848663095
817.2704190467886 531.0134330643327
428.3427093659793 900.3915824770534
865.3407206483803 418.56738037564725
144.77926092794456 819.9557261880506
771.6870807812111 906.7671278779325
564.3052988867427 625.9955512017058
692.3155161471233 797.1804928918176
371.2555900999214 673.737402704986
861.2898364468733 202.63202849168815
895.5551839965945 197.6714526482447
741.0062816258135 716.365293947955
117.75770696928146 425.4624036949415
781.7218640746396 242.80429667078974
835.842538183587 780.5986546348678
669.0294033370628 205.76494057059534
736.2339801770052 835.4314516690505
360.8230820232727 749.3814160418113
49.98039831530588 716.2948488703678
919.4005287573054 977.6763123512475
194.75890801409523 733.6861292362111
129.69878642953026 240.61770323853048
304.3476782134941 113.02536563052479
161.26266273004407 967.670016194812
829.4336664444803 835.3022818819768
79.39644952673008 574.2601568334059
457.10154047504005 761.9570331479155
840.0504555595044 522.243782520169
441.07448836878194 414.63103263155364
513.3464401784723 702.3712030791827
60.75566740301086 7.9629442305457765
872.2466474297054 924.9160596692124
334.3447090501165 592.3938251290195
155.72335557148597 454.04448397787723
299.78029018328834 453.98451125116844
769.8871885922078 202.16566333157803
146.9870465052915 239.53781108204498
925.883896777645 412.4200008324502
235.88059912687575 627.8565238221825
729.971051851614 400.6238034536086
566.8121380470794 751.7576633281094
39.03767165531502 202.40472154551625
583.6095803779468 990.5023428066129
473.93104072524204 776.9250383427957
284.09968571409274 198.59007831742525
343.3071632738808 755.5051808872379
488.9715219280957 914.4044904946534
872.3219897856585 591.6228600380523
777.0684925442633 600.9875186551398
53.333120671746336 368.17795102875215
33.67261431646884 511.2576588375605
639.8824146933346 448.57682573550693
778.0715114604528 341.2768560010029
290.58167718688145 620.1045935196652
437.6746280859165 437.7100437688949
636.1260009775277 371.21676797681744
518.1724047910332 959.4099194544845
90.50917749872534 468.7970370611865
182.70819023239426 58.09926009509625
556.6191455348458 57.09091643331055
97.75950522596466 839.411393656692
786.7413538966482 86.93988049473266
529.4016938718145 593.0891398661574
50.10064933095349 2.103992984165304
580.8537432864393 539.9311089899755
932.4228999690074 258.8757367209233
150.6822218005468 133.11373576361285
546.600125452167 435.85130080866463
660.7666034719667 772.8062202606368
3 4 5 10
1.0 1.0
2.0 2.0
3.0 3.0
100.0 100.0
20.0 20.0
30.0 30.0
53.0 3.0

I get:
4
0

Any other sample input and output would also be useful.
LL Cool Jay
LL Cool Jay
The Formula Wizard
Jason Winokur

sluga
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia
I had the exact same output.
Actually, the output is:
0
0

I got ACC after changing a line which said something like this:

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 )

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
[code/code]
Last edited by serur on Sun May 14, 2006 2:57 pm, edited 4 times in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Last edited by serur on Sun May 14, 2006 3:01 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
[/u]
Last edited by serur on Sun May 14, 2006 2:58 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Vahag
New poster
Posts: 5
Joined: Fri Dec 23, 2005 9:03 pm
Location: Armenia

### 10080 Gopher II WA

Can anyone help me I am getting WA

Code: Select all

``````#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
#define MAXV 250
#define MAXN 101
#define min(x,y) (x<y?x:y)

struct point
{
double x,y;
};

int G[MAXV][MAXV];
point gpos[MAXN],hpos[MAXN];
bool color[MAXV];
int p[MAXV];
int n,m,s,v;

double len(point p1,point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y -p2.y));
}

bool bfs(int,int);
int maxflow(int,int);

int main()
{
int i,j;
while(cin>>n>>m>>s>>v)
{
for(i=0;i<n;i++)
cin>>gpos[i].x>>gpos[i].y;
for(i=0;i<m;i++)
cin>>hpos[i].x>>hpos[i].y;
s*=v;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(len(gpos[i],hpos[j]) <= (double)s)
{
G[i+1][n+j+1] = G[n+j+1][i+1] = 1;
}
}
for(i=1;i<=n;i++)
G[0][i] = G[i][0] = 1;
for(j=n+1;j<=n+m;j++)
G[n+m+1][j] = G[j][n+m+1] = 1;
cout<<n - maxflow(0,n+m+1)<<endl;
for(i=0;i<MAXV;i++)
for(j=0;j<MAXV;j++)
G[i][j] = 0;
}
return 0;
}
bool bfs(int s,int t)
{
int i,u;
queue<int> Q;
for(i=0;i<=n+m+1;i++)
{
color[i] = 0;
p[i] = -1;
}
color[s] = 1;
Q.push(s);
while(!Q.empty())
{
u = Q.front();
if(u == t)
return true;
Q.pop();
for(i=0;i<=n+m+1;i++)
{
if(G[u][i] && !color[i])
{
p[i] = u;
color[i] = 1;
Q.push(i);
}
}
}
return false;
}

int maxflow(int s,int t)
{
int mf =0 ,i,j,m;
while(bfs(s,t))
{
i = t;
m = 100000;
while(p[i]!=-1)
{
j = p[i];
m = min(m,G[j][i]);
i = j;
}

i = t;
while(p[i]!=-1)
{
j = p[i];
G[j][i]-= m;
G[i][j]+=m;
i = j;
}
mf+=m;
}
return mf;
}``````

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10080 Gopher II WA

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.

Vahag
New poster
Posts: 5
Joined: Fri Dec 23, 2005 9:03 pm
Location: Armenia

### WA

Can anyone check whats wrong in my code it gives WA

Code: Select all

``````#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
#define MAXV 250
#define MAXN 101
#define min(x,y) (x<y?x:y)

struct point
{
double x,y;
};

int G[MAXV][MAXV];
point gpos[MAXN],hpos[MAXN];
bool color[MAXV];
int p[MAXV];
int n,m,s,v;

double len(point p1,point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y -p2.y));
}

bool bfs(int,int);
int maxflow(int,int);

int main()
{
int i,j;
while(cin>>n>>m>>s>>v)
{
for(i=0;i<n;i++)
cin>>gpos[i].x>>gpos[i].y;
for(i=0;i<m;i++)
cin>>hpos[i].x>>hpos[i].y;
s*=v;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(len(gpos[i],hpos[j]) <= (double)s)
{
G[i+1][n+j+1] = G[n+j+1][i+1] = 1;
}
}
for(i=1;i<=n;i++)
G[0][i] = G[i][0] = 1;
for(j=n+1;j<=n+m;j++)
G[n+m+1][j] = G[j][n+m+1] = 1;
cout<<n - maxflow(0,n+m+1)<<endl;
for(i=0;i<MAXV;i++)
for(j=0;j<MAXV;j++)
G[i][j] = 0;
}
return 0;
}
bool bfs(int s,int t)
{
int i,u;
queue<int> Q;
for(i=0;i<=n+m+1;i++)
{
color[i] = 0;
p[i] = -1;
}
color[s] = 1;
Q.push(s);
while(!Q.empty())
{
u = Q.front();
if(u == t)
return true;
Q.pop();
for(i=0;i<=n+m+1;i++)
{
if(G[u][i] && !color[i])
{
p[i] = u;
color[i] = 1;
Q.push(i);
}
}
}
return false;
}

int maxflow(int s,int t)
{
int mf =0 ,i,j,m;
while(bfs(s,t))
{
i = t;
m = 100000;
while(p[i]!=-1)
{
j = p[i];
m = min(m,G[j][i]);
i = j;
}

i = t;
while(p[i]!=-1)
{
j = p[i];
G[j][i]-= m;
G[i][j]+=m;
i = j;
}
mf+=m;
}
return mf;
}``````

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: WA

Vahag wrote:Can anyone check whats wrong in my code it gives WA
Rewrite the following so it won't use sqrt() and will compare with some epsilon tolerance. It may help:
Vahag wrote:
• double len(point p1,point p2)
{
• return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y -p2.y));
}

int main()
{
• ...
if(len(gpos[i],hpos[j]) <= (double)s)
{
• G[i+1][n+j+1] = G[n+j+1][i+1] = 1;
}
...
}

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi Vahag

I have changed ur code only this part and u got AC

Code: Select all

``````for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
double l = len(gpos[i],hpos[j]);
if( l < s || (l - s) < 1e-7)
{
G[i+1][n+j+1] = 1;
}
}
``````

Code: Select all

``````for(i=1;i<=n;i++)
G[0][i] = 1;
for(j=n+1;j<=n+m;j++)
G[j][n+m+1] = 1;
``````
Thankx
Mohiul Alam Prince

Vahag
New poster
Posts: 5
Joined: Fri Dec 23, 2005 9:03 pm
Location: Armenia
Thanks for help

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
can anyone please tell me why my max flow solution gives Runtime Error?

Code: Select all

``````#include <cstdio>
#include <cstdlib>
#include <queue>
#include <math.h>

using namespace std;

double d (int x1, int y1, int x2, int y2) {
return sqrt ((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

int a[300][300],p[300];
bool u[300];
int n,m,s,v,i,j,ans,flow;

int mmin (int a, int b) {
return (a<b)?a:b;
}

int findflow (int k) {
if (p[k]==-1)
return 30000;
else {
int x = findflow (p[k]);
return mmin (x,a[p[k]][k]);
}
}

void rebuild (int k) {
if (p[k]==-1) return;
rebuild (p[k]);
a[p[k]][k] -= flow;
a[k][p[k]] += flow;
}

int main(int argc, char* argv[]) {

double xh[300],yh[300],x[300],y[100];
queue <int> q;

while (scanf ("%d %d %d %d",&n,&m,&s,&v) == 4) {
for (i=0; i<300; i++) {
x[i] = 0;
y[i] = 0;
xh[i] = 0;
yh[i] = 0;
p[i] = 0;
u[i] = false;
for (j=0; j<300; j++)
a[i][j] = 0;
}
for (i=1; i<=n; i++) {
a[0][i] = 1;
scanf ("%lf %lf",&x[i],&y[i]);
}
for (i=1; i<=m; i++) {
a[n+i][n+m+1] = 1;
scanf ("%lf %lf",&xh[i],&yh[i]);
}

for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if ((d(x[i],y[i],xh[j],yh[j])/(v*1.0)) - s < 1e-6)
a[i][j+n] = 1;
else
a[i][j+n] = 0;

ans = 0;

while (true) {
for (i=0; i<=n+m+1; i++) {
u[i] = false;
p[i] = -1;
}
u[0] = true;
q.push (0);

while (!q.empty()) {
j = q.front ();
q.pop ();
for (i=0; i<=n+m+1; i++)
if (a[j][i]>0 && !u[i]) {
u[i] = true;
p[i] = j;
q.push(i);
}
}

if (p[n+m+1]==-1) break;

flow = findflow (n+m+1);
ans += flow;
rebuild (n+m+1);

}

printf ("%d\n",n-ans);

}

return 0;
}
``````
Now I lay me down to sleep...
my profile