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
razor123:
20161107 07:36:59
O(N^2M) vs O(NM^2)> dinic vs edmond's karp 

rakeshs:
20161025 19:06:52
how to see solutions? 

Rohit Agarwal:
20160805 13:05:30
Hello,


Priyank:
20160514 16:59:09
@akshu1995, Everything is correct. In input they are giving capacity. So when you will convert in equivalent directed graph you will get 3>4 and 4>3 capacity = 6. 

ian9696:
20160505 17:56:19
FIFO pushrelabel with gap heuristic gives AC


akshu1995:
20160503 08:21:03
The answer to the specified test case should have been 3 rather 5. 

Mariusz Trela:
20160311 22:03:16
A simple Dinic with complexity O(N^2*M) passes... I didn't expect that. 

sigma_poet:
20160110 05:57:59
Dinic 's time is O(N^2*M)， but N is 5000 and M is 30000. Will it get a pass ??? I'm not sure. 

Dario Pavlovic:
20150730 17:04:32
yup, a well written dinic works. 

dfranzen:
20150714 01:01:59
dinic's algorithm works ;) Last edit: 20150714 01:09:48 
Added by:  Neal Wu 
Date:  20090325 
Time limit:  2.766s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 