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/.


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

hide comments
2014-06-06 20:03:13 Hassan H. Monfared
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.
2014-03-05 07:01:23 epsilon_0
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.
2014-02-01 10:41:16 twilight
Relabel to Front gets TLE while ISAP gets AC...
2013-10-24 23:30:45 beginner
I am using push relable with FIFO heuristics and getting WA, what is meant by duplicate edges, I mean if I have an edge from u to v of weight w1 and if another edge is also from u to v and of weight w2, should I say that weight of edge (u,v) is w1+w2?
2013-09-17 13:20:36 beginner
Will fordFulkerson work?
Edit : what about push relable?

Answer: Ford Fulkerson will get TLE

Last edit: 2013-10-24 20:55:36
2012-08-22 10:34:29 dawei
In Average Dinic is very fast.
2011-04-15 16:53:12 John Mario
@vijay: This is not solved with Dijkstra's algorithm... you should read a bit more about Flows and then come back and give a it a shot
2011-04-09 17:17:05 vijay
this is a simple dijkstra's algo. problem,
please correct me if i m wrong,since i am getting WA
2010-10-28 07:08:28 Race with time
Test cases are not hard enough.
Yory: You may try this one, exactly the same statement but more difficult cases:
https://vn.spoj.pl/problems/FFLOW/
2010-09-16 20:52:31 vi002
Why Dinic algorithm got AC? It's complexity is O(V*V*E), so it's too slow for these restrictions.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.