I note also that the analysis on that page says that finding max flow by capacity scaling is O(V^4 log F) with F the maximum value of the flow, but this is not as tight as the bound conventionally given (at least, what's in my copy of CLRS), which is O(E^2 log C) = O(V^4 log C) with C the maximum capacity of an edge (we may ignore the infinite edges here provided the max flow is finite). Due to the log this doesn't make a huge a difference but it is significant (approx. 2.5x)
On Apr 29, 1:19 pm, "[email protected]" <[email protected]> wrote: > 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.
