753  A Plug for UNIX
Moderator: Board moderators

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
753 plug for Unix
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
Kalo mau kaya, buat apa sekolah?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Code: Select all
[laptopB>  >BX>  >XA>  >A]
[pager B>  >B]
[phone C>  >C]
[comb X>  >XD>  >D]

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
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
Kalo mau kaya, buat apa sekolah?

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
753  A Plug for UNIX
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 FordFulkerson 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 FordFulkerson 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
not specified
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
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
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
753  A plug for UNIX
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[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?
Attitude is no substitute for competence.
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.
753  A plug for UNIX
I use the highestlabel preflowpush algorithm for max flow. To find the node with the "highestlabel" 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