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
Hassan H. Monfared:
2014-06-06 20:03:13
FordFolkerson : O(|E|*|F| ) where |F| is max flow, so it depends on |F| which in this problem it can be up to 30,000*10^9. ~= 10^13
|
|
epsilon_0:
2014-03-05 07:01:23
I submitted the code by both Dinic and Push Relabel FIFO with gap heuristic, and they got a TLE.
|
|
twilight:
2014-02-01 10:41:16
Relabel to Front gets TLE while ISAP gets AC... |
|
beginner:
2013-10-24 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:
2013-09-17 13:20:36
Will fordFulkerson work?
|
|
dawei:
2012-08-22 10:34:29
In Average Dinic is very fast. |
|
John Mario:
2011-04-15 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:
2011-04-09 17:17:05
this is a simple dijkstra's algo. problem,
|
|
Race with time:
2010-10-28 07:08:28
Test cases are not hard enough.
|
|
vi002:
2010-09-16 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: | 2009-03-25 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |