Well "similar edge" is decidely unambiguous, it means the same edge as described in the "connection graph" with an infinite capacity. The issue is that the source/sink description seems flipped; you should have edges from the source to positive value towers, and edges from negative value towers to the sink. That way if we choose a negative value tower, its edge contributes to the cut value (and therefore subtracts from S-C).
On Apr 18, 9:48 pm, Alva Lin <[email protected]> wrote: > Problem:http://code.google.com/codejam/contest/311101/dashboard#s=p3&a=3 > > Official > Explanation:http://code.google.com/codejam/contest/311101/dashboard#s=a&a=3 > > In official explanation, it says: > To reduce the problem to an instance of MIN-CUT, we create a flow network > as follows. > Create a source vertex, a sink vertex, and one vertex for each tower. > Suppose a tower has score s. If s > 0, create an edge from the vertex to > the sink with capacity s. > If s < 0, create an edge from the source to this vertex with capacity |s|. > Finally, for every edge in the connection graph, create a similar edge in > the flow network with infinite capacity. > > Does the last sentence (... similar edge ...) means > "If a tower A has another tower B in its range, we represent this fact as a > directed edge from A to B."? > It seems that the sample input will form a zero-flow graph. > > Or the last sentence (... similar edge ...) means > "If a tower A has another tower B in its range, we represent this fact as a > directed edge from B to A."? > It seems that the sample input will form a meaningful graph. > But this is not what official explanation said in the "Connection graph" > section. > > Does anyone else feel that the pharse "similar edge" is quite ambiguous? > What's the true meaning of "similar edge"? -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
