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
coderdhanraj:
20230903 18:12:45
1. Those who don't getting how example is 5 rather than 3 you had to make flow in both of the directions.


lokesh_2052:
20210808 11:39:02
@tjandra most of people didn't do this in C because most of people including me using template or built in code write the algorithm . Sorry if someone get offend. 

dhruvgheewala:
20210324 10:38:08
Getting WA on testcase 11, any idea??


sarkybastard:
20200924 23:26:53
WA on test 11? Nope, WA on any test up to and including 11. 

nemesys:
20200924 04:54:00
WA on test 11, why? 

aks_010:
20200524 09:18:09
I am getting TLE on test case 11 using FordFulkerson Algo. Does it need to be done using Dinic Algo? Last edit: 20200524 09:19:05 

tarun2619:
20181116 15:50:10
@magmine Since a flow network is directed and the edges given here are undirected. So, for every undirected edge {u, v}, we must add 2 directed edges to our flow network, (u, v) and (v, u) each of capacity w. Your mistake might be adding only a directed edge from u to v of weight w and not the other edge from v to u of the same weight. 

magmine:
20181106 16:51:34
Please some help, I'm using FordFulkerson algorithm to solve this problem, but this algorithm gives as solution to the example test case 3 rather than 5, Can some one point out why ? 

saihemanth9019:
20180512 19:23:50
WA in Test Case 11 :/ Any idea why? Last edit: 20180512 19:29:45 

prakharrrr4:
20180107 05:19:16
" Note that it is possible for there to be duplicate edges, as well as an edge from a node to itself."

Added by:  Neal Wu 
Date:  20090325 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 