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 ≤ 10^{9}) 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 32bit 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 maxflow, 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 mincut, 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:
20140201 10:41:16
Relabel to Front gets TLE while ISAP gets AC... 

beginner:
20131024 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:
20130917 13:20:36
Will fordFulkerson work?


dawei:
20120822 10:34:29
In Average Dinic is very fast. 

John Mario:
20110415 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:
20110409 17:17:05
this is a simple dijkstra's algo. problem,


Race with time:
20101028 07:08:28
Test cases are not hard enough.


vi002:
20100916 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:  20090325 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 