10080 - Gopher II

[Shahid]

is this problem is completely a maximum bipartite matching problem?

or it just like that, not totaly a bipartite matching problem....?

actually i need to know that seriously ........ cauze i am working on a algorithm of finding maximum bipartite matching of a graph.

if this is completely a maximum bipartite matching problem, then i could test my algorithm on the dataset of this problem to verify the algorithm's correctness .....

thanx for ur response

- Shahid

[turuthok]

It sure looks like max. cardinality bipartite matching. Left side the gophers, right side the holes. If gopher i can reach hole j given the constraints, then the capacity between gopher i and hole j is 1, .. zero otherwise.

-turuthok-

[Hisoka]

Hello, can you help me ? I got WA for many time for this problem
input:

Code: Select all

9 16 13 6
16.222222 8.394495
506.466667 236.028571
127.750000 82.933333
8.650000 13.100000
30.257732 30.935185
6.500000 8.100000
226.125000 35.500000
88.606061 53.427350
105.948276 67.800000
66.600000 69.363636
303.500000 107.333333
103.888889 59.470588
87.600000 81.272727
43.333333 52.500000
48.800000 29.611111
3.300000 4.812500
16.333333 10.812500
6.500000 4.437500
9.444444 9.888889
221.000000 156.666667
85.714286 57.250000
70.500000 107.000000
100.000000 24.600000
26.333333 27.555556
96.250000 56.125000

output:

Code: Select all

2

Is that true ?

Thanks for help....

[cytse]

Yes you are right.

[Hisoka]

Okay thanks for you cytse. But I got WA again, I don't know why ?
for input:

Code: Select all

33 38 17 21
92.014706 49.404580
89.269841 37.428571
203.612245 179.950000
143.384615 37.859155
47.546512 27.339869
80.448718 38.132948
116.550000 55.570370
960.222222 525.722222
105.405797 57.176471
105.558140 60.522727
56.657143 34.593496
2908.000000 113.976190
79.230769 62.592593
299.437500 84.964912
10.868421 9.806452
33.281250 53.909091
4.848485 7.251613
39.898551 38.010309
99.210526 48.440000
5.606557 13.815789
131.253731 76.242188
169.800000 78.142857
1453.166667 593.250000
178.250000 110.750000
327.050000 82.727273
40.153061 37.873016
73.630769 51.740000
107.033708 91.478261
6.217391 13.380952
151.407407 94.088889
85.520548 57.475410
246.040000 87.315068
36.712329 17.591716
165.500000 92.500000
4.666667 5.833333
32.000000 8.400000
66.000000 33.333333
66.625000 62.666667
129.333333 100.000000
126.000000 84.000000
33.500000 18.062500
192.250000 162.000000
85.000000 39.714286
96.400000 61.176471
418.000000 463.500000
13.750000 13.454545
227.250000 185.000000
66.400000 36.052632
172.250000 110.285714
541.000000 75.250000
33.285714 20.312500
133.666667 62.125000
118.400000 92.857143
129.666667 91.200000
147.500000 82.000000
33.600000 14.916667
111.500000 28.000000
71.222222 77.888889
99.000000 57.692308
140.500000 71.000000
5.300000 5.600000
13.000000 12.666667
81.333333 70.375000
63.250000 30.444444
27.125000 18.571429
27.000000 38.375000
2.333333 2.888889
66.700000 42.375000
393.000000 54.375000
185.400000 71.285714
31.900000 32.153846

output:

Code: Select all

3

Is that right to ?

this is my code :
[c]int result(int n, int m)
{
int i,j,k,min,count=0;
while(1){
for(i=0,min=0;i<n;i++) if(n_adj1){ min=1; break; }
if(!min) break;
for(i=0,min=1000;i<n;i++)
if(min>n_adj1&&n_adj1){ min=n_adj1; j=i; }
for(i=0,min=1000;i<m;i++)
if(adj[j]){
if(min>n_adj2){ min=n_adj2; k=i; }
--n_adj2;
}
for(i=0;i<m;i++) adj[j]=0;
for(i=0;i<n;i++)
if(adj[k]){
adj[i][k]=0;
--n_adj1[i];
}
n_adj2[k]=0; n_adj1[j]=0;
count++;
}
return count;
}[/c]
I have adj[][] where row is hole, and collums is gopher.
m is number of gopher. and n is number of hole.
n_adj1[] is sum of gopher that can run into this hole.
n_adj2[] is sum of hole where this gopher can run into.
and for output I use:
[c]printf("%d\n",m-result(n,m));[/c]

is that true ?
I'm sorry for my bad english.

Thanks for help....

[LittleJohn]

output:

Code: Select all

3

Is that right to ?

Yes, the answer is right.
Sorry, I feel a little sick and do not try to understand your method in detail.
But I think it's a max-flow problem..

[Hisoka]

hello little john.....

thanks for your answer, maybe I must check again my program tomorow, because I'm very tired now. But maybe you can give me sample if you want.

once again, thanks.......

[LittleJohn]

Hi, I don't have any boundary case.
But if you want, you can write a random input generator and send it with your code to me.
I'll compare your output with mine.
My E-mail: u881510@oz.nthu.edu.tw

[Hisoka]

okay, I'll send it to you.

Thanks for help...

[Amir Aavani]

hello everyone
i think it is a matching on a bipartie graph.
i myself solve this problem by making a biparite graph G,
in which G[i,j] is True if gopher can reach to hole[j], and otherwise set it to False.
then i run my FindBipariteMatch on G

[Steven Halim]

For Hisoka,

From your examples, I think you are trapped like me
You assume the input is only 1 case... (since the sample input is like that)

>> The input contains several cases. !!!

So, if the input (taken from sample input) is:

Code: Select all

2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

Then the output:

Code: Select all

1
1

Try it

[Hisoka]

My program handle that. So I think I have problem with my algorithm. I use pure algorithm for this problem, and I'm still comfuce why my program got WA. From previous message, this problem must be solved with max-flow.

Can you find a sample IO that can break my previous algo ?

[mlvahe]

WHY TLE????
Ignore my comments thay are in Armenian.
[cpp]#include <iostream.h>
#include <math.h>

const int NMAX = 400;

int graph[NMAX][NMAX], para[NMAX], cep[NMAX], q[NMAX][NMAX], qn[NMAX], unused[NMAX];
double x[NMAX], y[NMAX];
main()
{
//kardal u karucel graphy
int n, m, v, s, vulner, k, i, j, b, stop;
while(cin >> n >> m >> v >> s)
{
s *= v;
b = true;
for (i = 0; i < n+m; i++)
{
para = -1;
for (j = 0; j < n+m; j++)
graph[j] = 0;
cin >> x >> y;
}
for (i = 0; i < n; i++)
for (j = n; j < n+m; j++)
{
graph[j] = (sqrt((x-x[j])*(x-x[j])+(y-y[j])*(y-y[j])) <= s);
graph[j] = graph[i][j];
if (b && graph[i][j])
{
b = false;
para[i] = j;
para[j] = i;
}

}
//Initialization
b = true;
while (b)//qani der hnaravor e karucel ceredujushschaja cep
{
//karucel cepy
//<-
//lcnel makardaknery
for (i = 0; i < n; i++)
if (para[i] == -1)
{
q[0][qn[0]] = i;
qn[0]++;
}
for (i = 0; i < n+m; i++)
unused[i] = 1;
stop = 0;
for (k = 0; qn[k] != 0; k++)
{
if (k % 2 == 0)
{
for (i = 0; i < qn[k]; i++)
{
for (j = n; j < n+m; j++)
if (para[q[k][i]] != j && graph[q[k][i]][j] && unused[j])
{
q[k+1][qn[k+1]] = j;
qn[k+1]++;
unused[j] = 0;
if (para[j] == -1)
{
stop = 1;
break;
}
}
if (stop)
break;
}
}
else
{
for (i = 0; i < qn[k]; i++)
if (unused[para[q[k][i]]])
{
q[k+1][qn[k+1]] = para[q[k][i]];
qn[k+1]++;
unused[para[q[k][i]]] = 0;
}
}
if (stop)
break;
}
//gcel cepi toxy
if (!stop)
{
b = false;
break;
}
cep[k+1] = q[k+1][qn[k+1]-1];
for (i = k; i >= 0; i--)
for (j = 0; j < qn[k]; j++)
if (graph[cep[i+1]][q[k][j]])
cep[i] = q[k][j];
//->
k++;
//update parasachetanian
for (i = 0; i <= k; i++)
if (i % 2 == 0)
{
para[cep[i]] = cep[i+1];
para[cep[i+1]] = cep[i];
}
}
vulner = 0;
for (i = 0; i < n; i++)
if (para[i] == -1)
vulner++;
cout << vulner << "\n";
}
return 0;
}[/cpp]

[Minilek]

[c]
AC
[/c]

[shamim]

Your code seems to get Compiler error. Please check if it is correct.