### 753 plug for Unix

Posted:

**Thu Dec 11, 2003 5:46 pm**hi,

can you tell me how to get 1 in sample input / output?

thanks before.

regards,

titid

can you tell me how to get 1 in sample input / output?

thanks before.

regards,

titid

Page **1** of **2**

Posted: **Thu Dec 11, 2003 5:46 pm**

hi,

can you tell me how to get 1 in sample input / output?

thanks before.

regards,

titid

can you tell me how to get 1 in sample input / output?

thanks before.

regards,

titid

Posted: **Thu Jan 22, 2004 12:08 pm**

Code: Select all

```
[laptop|B> -- >B|X> -- >X|A> -- >A]
[pager |B> -------------------- >B]
[phone |C> -------------------- >C]
[comb |X> -- >X|D> ----------- >D]
```

Posted: **Sat Jan 24, 2004 6:51 am**

thanks for your explanation.

another ask, what is the output for

is the output 0 or 1?

thanks before.

-titid-

another ask, what is the output for

Code: Select all

```
1
1
A
1
titid B
1
A B
```

thanks before.

-titid-

Posted: **Sat Jan 24, 2004 10:17 am**

1

Posted: **Mon Jan 26, 2004 6:48 am**

thanks little joey. at first some statements confused me as i always got WA. but i found a little bug in my code. now i got AC. thank you very much

Posted: **Thu Mar 18, 2004 1:37 am**

Hi,

Looks like a simple bipartite matching problem, but I always get a WA reply What I'm doing is:

- plugs and receptacles (verticies) together with adapters (edges) form a graph, so first I do a bsf of this graph for each device (of course, if two devices have got the same plug type I do only one bfs) and so I get for each device a list of receptacles it can be plugged in (directly or through a chain of adapters);

- devices together with lists of receptacles they can be plugged in form a bipartite graph, so I use Ford-Fulkerson method to find the max flow;

- number of devices minus max flow is the result.

I've tried different tests, but all of them passed. Can anyone suggest some interesting tests?

And another question. Is the following input vaild?

So laptop has got two plugs. Are we garanted that each device appears only once in the list?

Thanks,

ab

Looks like a simple bipartite matching problem, but I always get a WA reply What I'm doing is:

- plugs and receptacles (verticies) together with adapters (edges) form a graph, so first I do a bsf of this graph for each device (of course, if two devices have got the same plug type I do only one bfs) and so I get for each device a list of receptacles it can be plugged in (directly or through a chain of adapters);

- devices together with lists of receptacles they can be plugged in form a bipartite graph, so I use Ford-Fulkerson method to find the max flow;

- number of devices minus max flow is the result.

I've tried different tests, but all of them passed. Can anyone suggest some interesting tests?

And another question. Is the following input vaild?

Code: Select all

```
2
A
B
3
laptop A
laptop B
phone A
0
```

Thanks,

ab

Posted: **Sun Mar 21, 2004 12:01 am**

Argh! My algorithm is OK, but I've forgotten to initialize some variable in my program and that's why I was getting WA It took me two weeks to find that stupid mistake!!!

Posted: **Sat Aug 21, 2004 2:35 pm**

4

4

c

c

c

c

4

lap1 a

lap2 b

lap3 a

lap4 x

4

x c

b x

a b

y x

5

d

c

d

c

c

5

lap1 a

lap2 a

lap3 b

lap4 b

lap5 b

5

x c

b x

a b

y x

x d

3

p

q

r

3

lap1 p

lap2 p

lap3 p

2

p q

p r

3

c

c

c

3

lap1 a

lap2 b

lap3 b

3

a c

b a

a b

0

0

0

0

Posted: **Sat Aug 21, 2004 2:39 pm**

Ahhh... Are you getting WA or are you giving free sample i/o to those who are getting WA.Mahmud wrote: Sample input:

4

4

c

c

c

c

4

lap1 a

lap2 b

lap3 a

lap4 x

4

x c

b x

a b

y x

5

d

c

d

c

c

5

lap1 a

lap2 a

lap3 b

lap4 b

lap5 b

5

x c

b x

a b

y x

x d

3

p

q

r

3

lap1 p

lap2 p

lap3 p

2

p q

p r

3

c

c

c

3

lap1 a

lap2 b

lap3 b

3

a c

b a

a b

Sample Output:

0

0

0

0

Posted: **Tue Feb 22, 2005 1:09 am**

I can't find out what's wrong... Let's say we have a total of nrrec plugs or receptacles. While reading the input data I always check if the plug has been read before. If not, I increase nrrec and add it. For each of the m devices I have ptr* - the number of the plug / receptacle of the i'th device.*

Then I build a matrix mat*[j] (i, j = 1..nrrec), mat**[j] = 1 means that that the device i can be plugged in the j receptacle. First, mat**[j] = 1 if i = j, or 0 otherwise. Then, considering the k pair of adapters, if x and y are a pair of numbers, mat[x][y] = 1.*

Using this information I do nrrec df searches to find out the final mat*[j].*

After that there's a bipartite graph with 0 - the source, 1..m - the devices, m+1..m+n - the receptacles, and n+m+1 - the destination. The capacity of (s, x) is 1 for x = 1..m, the capacity of (x, d) is 1 for x = m+1.. n+m. The capacity of (x, y) is 1 if mat[ptr*][j] = 1 (we can plug the i'th device in the j'th receptacle).*

The answer is m - the maximum flow in this graph. Can anybody tell where my mistake is?

Then I build a matrix mat

Using this information I do nrrec df searches to find out the final mat

After that there's a bipartite graph with 0 - the source, 1..m - the devices, m+1..m+n - the receptacles, and n+m+1 - the destination. The capacity of (s, x) is 1 for x = 1..m, the capacity of (x, d) is 1 for x = m+1.. n+m. The capacity of (x, y) is 1 if mat[ptr

The answer is m - the maximum flow in this graph. Can anybody tell where my mistake is?

Posted: **Tue Feb 22, 2005 3:31 pm**

Your Algorithm looks basically correct as it is indeed a MAX flow problem.

But here is how I considered it.

suppose there is one source, some adapters , some device, and one sink.

The capacity from source to adapters is infinite( if the shop has supply ), the capacity of adapters to adapters is also infinite, and the capacity of adapters to device is one and capactiy of device to sink is also one.

Well, I know my explanation is vague, but try to make something out of it.

But here is how I considered it.

suppose there is one source, some adapters , some device, and one sink.

The capacity from source to adapters is infinite( if the shop has supply ), the capacity of adapters to adapters is also infinite, and the capacity of adapters to device is one and capactiy of device to sink is also one.

Well, I know my explanation is vague, but try to make something out of it.

Posted: **Wed Feb 23, 2005 12:18 am**

My solution seems easier.. I have only n+m+2 vertices, and the i'th device is connected to the j'th plug with a 1-capacity edge only if we can connect the two, using any kind of adapter.

This should be right too... but it keeps wa-ing.

This should be right too... but it keeps wa-ing.

Posted: **Sun May 01, 2005 12:47 am**

This input is invalid. There is at most 1 of each type of socket. I checked this with an assert().

Posted: **Thu May 05, 2005 11:37 am**

I use the highest-label preflow-push algorithm for max flow. To find the node with the "highest-label" I use a heap (push_heap & pop_push from STL with a Less functor for key comparison). My submissions all end up with a runtime error (SIGSEGV). After checking many times I still can't find the code segment which may have caused that. Here is my code:

Code: Select all

```
Deleted by a lazy admin
```

Posted: **Thu May 05, 2005 2:27 pm**

There can be more than 300 plug names in the input - each of the 100 adapters may introduce up to two new plug names. Increase your MAX constant to something like a 500.

Also, your program does not print a blank line between test cases.

Also, your program does not print a blank line between test cases.