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
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."
|
|
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,
|
|
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
|
|
akshu1995:
2016-05-03 08:21:03
The answer to the specified test case should have been 3 rather 5. |
|
Mariusz Trela:
2016-03-11 22:03:16
A simple Dinic with complexity O(N^2*M) passes... I didn't expect that. |
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 |