Run BFS from source Z. Save distance of each node from Z.

For each node, set the flow of this node = ari. Push all the nodes in the queue according to their distance from Z. In descending order.

Run another BFS. You don't need to push any node in the queue.

For each node in front of the queue, push its flow by checking the capacity of the edge to its current child(To it's parent according to previous BFS).

After finishing the BFS, the total flow of node Z is the solution.

Don't forget to use long long int data type to store the solution.

This problem can be solved by a single DFS also. Think!


82% Solution Ratio
dontquitEarliest, Mar '20
rayhan_labibFastest, 0.4s
user.479611Lightest, 86 MB
Yasir_ArafatShortest, 570B
Toph uses cookies. By continuing you agree to our Cookie Policy.