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/.


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

hide comments
2024-06-16 16:29:58
BFS Ford-Fulkerson get TLE? There is still a faster way for this problem?

i use push-relabel this time (https://cp-algorithms.com/graph/push-relabel-faster.html) and still get TLE :))

Last edit: 2024-06-17 11:13:34
2024-04-24 23:00:07
Why does Dinitz (with scaling) work here? Isn't that O(VElog(U)) ? I am new to flow graphs, Please be 'less' harsh on me...
(I have heard that it's usually much faster in practice).
2023-09-03 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.
2. Those who are getting WA on test 11. use long long and maxFlow as 1e18 or something maybe > 1e15.
2021-08-08 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.
2021-03-24 10:38:08
Getting WA on testcase 11, any idea??
I am adding undirected edges and used int64_t, which is i guess more than sufficient.

Edit: Resolved, implementation issue !!

Last edit: 2021-03-24 19:03:09
2020-09-24 23:26:53
WA on test 11? Nope, WA on any test up to and including 11.
2020-09-24 04:54:00
WA on test 11, why?
2020-05-24 09:18:09
I am getting TLE on test case 11 using Ford-Fulkerson Algo. Does it need to be done using Dinic Algo?

Last edit: 2020-05-24 09:19:05
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.
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 ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.