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
tarun2619: 2018-11-16 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: 2018-11-06 16:51:34

Please some help, I'm using Ford-Fulkerson 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: 2018-05-12 19:23:50

WA in Test Case 11 :/ Any idea why?

Last edit: 2018-05-12 19:29:45
prakharrrr4: 2018-01-07 05:19:16

" Note that it is possible for there to be duplicate edges, as well as an edge from a node to itself."
what to do about that ?

person123456: 2017-06-11 07:48:05

don't forget to use long long

razor123: 2016-11-07 07:36:59

O(N^2M) vs O(NM^2)---> dinic vs edmond's karp

rakeshs: 2016-10-25 19:06:52

how to see solutions?

Rohit Agarwal: 2016-08-05 13:05:30

Hello,
My "push front relabel" algorithm is failing in test case 11. Can someone please give me some trick tc's?

Priyank: 2016-05-14 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: 2016-05-05 17:56:19

FIFO push-relabel with gap heuristic gives AC
while TLE without using heuristic


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