×

PUSHFLOW - Editorial

Author: Constantine Sokol
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

Hard

PREREQUISITES:

Segment Tree, Heavy Light Decomposition, Flow

PROBLEM:

Given a graph G, consisting of N vertices and M edges, each edge has a positive capacity and each vertex of G belongs to at most one simple cycle.

You task is to implement a data structure, which can process the following queries efficiently:

• 0 S T: find the maximum flow in G in case the source is S and the sink is T;
• 1 X NEW_CAPACITY: make the capacity of X'th edge equal to NEW_CAPACITY.

SOLUTION OUTLINES:

If you don't know about HLD you can read about it on the previous editorials etc. :).

Firstly, let's assume that the graph given to us consists of a single cycle. Than the solution is obvious: there are only two path between every two distinct vertices. We can simply maintain a segment tree of edges and that's it.

Secondly, let's assume that the graph given to us is a tree. That the solution is obvious as well: there's a single path between every two distinct vertices. We can use Heavy-Light Decomposition of tree in order to process all the queries and that's it.

OK, now let's go back to the problem as it is.

Tester's Approach

We consider a cycle as a node, then graph will be a tree. After this we do HL-decomposition, then each component will be like a (upper component) -- cycle -- cycle -- cycle -- cycle. (here cycle = a cycle or an ordinary node). We use a segment tree for each component of HLD, and we also use a segment tree for each cycle. Then we can calculate the maximum flow from some node to the nearest node of upper component of HLD in O(log N). And of course, we can calculate the maximum flow from some node to some node, if both nodes are in the same component in O(log N). The depth of HLD is O(log N), so we can calculate the maximum flow in O( (log N)^2 ).

The modification query is not difficult in this approach.
If the edge is in cycle, we modify this cycle, and then modify HLD. Otherwise, we just modify HLD.
It will be done in O(log N).

Author's Approach

Firsly, let's make our graph rooted(let's assume that the first vertex is the root). Now the processing of the queries is splited into two parts:
1. We need to raise both vertices A and B to the same cycle.
2. Then, just simply solve the problem of a cycle(described before).

So, the problem is to raise a single vertex to a cycle.

Let's do this for each cycle: we have a cycle 1 - 2 - 3 - 4 - ... - K, which consists of K vertices. Then, let's transform it into K - 1 edges 1 - 2, 1 - 3, 1 - 4, ..., 1 - K, where the capacity of edges 1 - L(for 1 < L <= K) is equal to the size of the flow, that can stream through the cycle from vertex L to the vertex 1.

If we have no modification queries, than the problem is easy: we simply transform our graph into a tree and then process all the queries the way described above.
But the problem is that we have modification queries. :)
If we modify the capacity of an edge, that doesn't belong to any cycle(let's call it a tree edge), then we can simply maintain such edges with HLDOT.
If we modify the capacity of an edge, that does belong to a cycle(let's call it a cycle edge), then we should:
A) Update the corresponding segment tree with the new capacity.
B) Update the capacity of all (K - 1) edges, that we built for the cycle of this cycle edge.

The problem is with B). If we update the capacity of a cycle edge, that belongs to a big cycle, then we should update a lot of edges and can lead to the TLE verdict.

But there are not so many big cycles. Let's call a cycle BIG if it contains at least sqrt( N ) vertices and SMALL otherwise. Then, for each small cycle we can simply update all the (K - 1) edges. For big cycle we won't maintain the edges in our HLDOT. We will store them separately. When we need to process a flow-query, we can simply loop through all the big cycles and calculate the size of the flow.

So, total complexity:

Preprocessing: O( N log N )
Change-query: O( log N ) for an tree edge, O( K * log N ) for an cycle edge of a small cycle, O( log N ) for an cycle edge of a big cycle.
Flow-query: O( ( log N ) ** 2 + T * log N ), where T equals to the number of big cycles.
The complexity of change-query won't exceed sqrt( N ) * log N.
The complexity of flow-query won't exceed sqrt( N ) * log N as well.

So, the solution runs in O( N log N + Q * sqrt( N ) * log( N ) )

AUTHOR'S AND TESTER'S SOLUTIONS:
Author's solution
Tester's solution

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

1

How can a O( N log N + Q * sqrt( N ) * log( N ) ) algo run under 1 sec!! o.O

(11 Aug '14, 15:55)

 4 To clarify: Author's solution doesn't get AC. It was meant to, but now it doesn't. The reason is that Hiroto(the Tester) has came up with a better one, so we decided to use his solution as the model one. Nevertheless, Author's approach is rather interesting, so we decided to share it with you. answered 11 Aug '14, 16:30 166●14●32●35 accept rate: 0% 1 His solution had a small bug, it's been fixed and updated solution has been put up. (11 Aug '14, 19:36)
 0 Really liked this problem, although didn't correctly solve it. I was wondering how I should start with these kind of problems. I immediately came up with the following and coded it in that sequence, very likely to tester solution: Preprocessing: dfs to detect cycles/bridges, each cycle is a node dfs to root the tree and immediately add LCA dfs to find heavy paths (heavy paths are also modeled with segment trees) Queries: Query: Min(flow(x,LCA(x,y),flow(y,LCA(x,y)) where flow(A,B) is letting A climbing up to B tracking the minimum, using heavy paths if any + if LCA(a,b) is a cycle then the min flow in that cycle is checked as well Update: update node + it's heavy path if node is on heavy path My solution I also made up some examples by hand which all passed. I still haven't found my bug(s). Is there a good general approach to start with these kind of problems? Or some ideas how I would be able to quickly find my bug(s)? answered 12 Aug '14, 04:27 5★samjay 427●1●5●10 accept rate: 10%
 0 Hi, I used the testers approach and got TLE. Despite attempting a lot of optimization I still failed to get and AC. Can you please tell me on which kind of test case I was failing? My Submission http://www.codechef.com/viewsolution/4548380 answered 13 Aug '14, 10:41 5★shahbaz 15 accept rate: 0%
 0 There is a easier algorithm using LCT. It runs in $O((n + q)\log n)$. I learnt it from wangyisong1996. For each cycle, we cut down the edge with the min flow and add its flow to all other edges on the cycle. Then this graph becomes a tree and we can use LCT to calculate the min edge on the path from x to y, which is the answer of query(x, y). As for modifies, we can maintain a heap for each cycle and maintain the LCT. The LCT should support two operations : query the min edge on a path, and add a number on all edges on a path. It's more intuitive than using segment trees on HLD and more easy to implement. Though its complexity is better, it runs slower than HLD, because of the large constant number of LCT. answered 19 Dec '15, 15:18 2★pb_ds 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,359
×711
×374
×55
×33

question asked: 11 Aug '14, 15:13

question was seen: 3,415 times

last updated: 19 Dec '15, 15:20