FASTFLOW - Fast Maximum Flow


Given a graph with N (2 ≤ N ≤ 5,000) vertices numbered 1 to N and M (1 ≤ M ≤ 30,000) undirected, weighted edges, compute the maximum flow / minimum cut from vertex 1 to vertex N.

Input

The first line contains the two integers N and M. The next M lines each contain three integers A, B, and C, denoting that there is an edge of capacity C (1 ≤ C ≤ 109) between nodes A and B (1 ≤ A, B ≤ N). Note that it is possible for there to be duplicate edges, as well as an edge from a node to itself.

Output

Print a single integer (which may not fit into a 32-bit integer) denoting the maximum flow / minimum cut between 1 and N.

Example

Input:
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3

Output:
5

Viewing the problem as max-flow, we may send 3 units of flow through the path 1 - 2 - 3 - 4 and 2 units of flow through the path 1 - 3 - 4. Viewing the problem as min-cut, we may cut the first and third edges. Either way the total is 5.

Note: see also http://www.spoj.com/problems/MATCHING/.


hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2015-05-28 16:35:09

very fun! among 931 accepted users (for now), only 10 of them using pure C language ;-)

dened: 2015-01-22 09:17:23

My solution using highest-label push-relabel algorithm was accepted even without any heuristics. But I had to implement an efficient data structure for the sparse graph.

Reza: 2014-12-23 13:41:26

Dinic --> Accepted. trust me :-"

Anuj Arora: 2014-11-30 20:54:09

Very hard problem.......too many TLE......phewww

master_blaster: 2014-08-29 17:14:41


Last edit: 2014-08-29 17:45:16
Luis Manuel D�az Bar�n: 2014-08-12 16:39:25

Edmonds-Karp TLE on test 11. It should be allowed to pass

Last edit: 2014-08-25 17:34:51
rahul kumar: 2014-08-07 20:56:07

can anybody tell me why im getting WA on 12th test

Anmol Pandey: 2014-07-15 13:37:33

Edmond-Karps algo gives TLE

Last edit: 2014-07-15 13:38:40
Hassan H. Monfared: 2014-06-06 20:03:13

FordFolkerson : O(|E|*|F| ) where |F| is max flow, so it depends on |F| which in this problem it can be up to 30,000*10^9. ~= 10^13
Edmond-Karps : O( |E|^2 * |V| ), could be up to 30k*30k*5k > 10^12
Push-Relabel : O( |V|^2 * |E|) ~= 5k*5k * 30k ~= 10^11.
So push relabel seems faster solution.

epsilon_0: 2014-03-05 07:01:23

I submitted the code by both Dinic and Push Relabel FIFO with gap heuristic, and they got a TLE.
Could someone give the reason for this?
I later submitted the code which implemented BFS search and it got AC.


Added by:Neal Wu
Date:2009-03-25
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO