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
twilight: 2014-02-01 10:41:16

Relabel to Front gets TLE while ISAP gets AC...

beginner: 2013-10-24 23:30:45

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?

beginner: 2013-09-17 13:20:36

Will fordFulkerson work?
Edit : what about push relable?

Answer: Ford Fulkerson will get TLE

Last edit: 2013-10-24 20:55:36
dawei: 2012-08-22 10:34:29

In Average Dinic is very fast.

John Mario: 2011-04-15 16:53:12

@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

vijay: 2011-04-09 17:17:05

this is a simple dijkstra's algo. problem,
please correct me if i m wrong,since i am getting WA

Race with time: 2010-10-28 07:08:28

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/

vi002: 2010-09-16 20:52:31

Why Dinic algorithm got AC? It's complexity is O(V*V*E), so it's too slow for these restrictions.


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