-
Notifications
You must be signed in to change notification settings - Fork 0
/
edmond_karp.cpp
137 lines (121 loc) · 3.69 KB
/
edmond_karp.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
/* This class implements a bit unusual scheme for storing edges of the graph,
* in order to retrieve the backward edge for a given edge quickly. */
class FlowGraph {
public:
struct Edge {
int from, to, capacity, flow;
};
private:
/* List of all - forward and backward - edges */
vector<Edge> edges;
/* These adjacency lists store only indices of edges in the edges list */
vector<vector<size_t> > graph;
public:
explicit FlowGraph(size_t n): graph(n) {}
void add_edge(int from, int to, int capacity) {
/* Note that we first append a forward edge and then a backward edge,
* so all forward edges are stored at even indices (starting from 0),
* whereas backward edges are stored at odd indices in the list edges */
Edge forward_edge = {from, to, capacity, 0};
Edge backward_edge = {to, from, 0, 0};
graph[from].push_back(edges.size());
edges.push_back(forward_edge);
graph[to].push_back(edges.size());
edges.push_back(backward_edge);
}
size_t size() const {
return graph.size();
}
const vector<size_t>& get_ids(int from) const {
return graph[from];
}
const Edge& get_edge(size_t id) const {
return edges[id];
}
void add_flow(size_t id, int flow) {
/* To get a backward edge for a true forward edge (i.e id is even), we should get id + 1
* due to the described above scheme. On the other hand, when we have to get a "backward"
* edge for a backward edge (i.e. get a forward edge for backward - id is odd), id - 1
* should be taken.
*
* It turns out that id ^ 1 works for both cases. Think this through! */
edges[id].flow += flow;
edges[id ^ 1].flow -= flow;
}
};
FlowGraph read_data() {
int vertex_count, edge_count;
std::cin >> vertex_count >> edge_count;
FlowGraph graph(vertex_count);
for (int i = 0; i < edge_count; ++i) {
int u, v, capacity;
std::cin >> u >> v >> capacity;
graph.add_edge(u - 1, v - 1, capacity);
}
return graph;
}
int max_flow(FlowGraph& graph, int s, int t) {
int flow = 0;
/* your code goes here */
//Edmond Karp Algorithm
while(1)
{
map<int, pair<int, int>> parent;
parent[s].first = -1;
parent[t].first = -1;
queue<int> q; // BFS Queue
set<int> v; // Visited Set
q.push(s);
while(!q.empty())
{
if(parent[t].first!=-1)
break;
int current = q.front();
q.pop();
v.insert(current);
for( auto & i:graph.get_ids(current))
{
FlowGraph::Edge e = graph.get_edge(i);
// Vertex is unvisited && capacity > flow && sink is !found
if((v.find(e.to)==v.end()) && (e.capacity > e.flow) && (parent[t].first==-1))
{
q.push(e.to);
parent[e.to].first = current;
parent[e.to].second = i;
v.insert(e.to);
}
}
}
if(parent[t].first!=-1) // we found a augmented path
{
// Find minimum flow of the augmented path
int min_flow = INFINITY;
int start =t;
do{
FlowGraph::Edge e = graph.get_edge(parent[start].second);
min_flow = min(min_flow, e.capacity-e.flow);
start = e.from;
}while(start !=s);
// Update Graph and residual
start =t;
do{
FlowGraph::Edge e = graph.get_edge(parent[start].second);
graph.add_flow(parent[start].second, min_flow);
start = e.from;
}while(start !=s);
flow += min_flow;
}
else // No Augmented path found break;
break;
}
return flow;
}
int main() {
std::ios_base::sync_with_stdio(false);
FlowGraph graph = read_data();
std::cout << max_flow(graph, 0, graph.size() - 1) << "\n";
return 0;
}