Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <queue>
- #include <limits.h>
- bool bfs(std::vector<std::vector<int> >& capacities, int s, int f, std::vector<int>& parents, int n) {
- std::queue<int> queue;
- std::vector<bool> visited(n, false);
- parents[s] = -1;
- visited[s] = true;
- queue.push(s);
- while (!queue.empty()){
- int from = queue.front();
- queue.pop();
- for (int i = 0; i < n; i++){
- if (!visited[i] && capacities[from][i] > 0) {
- queue.push(i);
- parents[i] = from;
- visited[i] = true;
- }
- }
- }
- return visited[f];
- }
- int edmonds_karp(std::vector<std::vector<int> >& capacities, int s, int f, int n){
- int u, v;
- std::vector<int> parents(n, -1);
- int max_flow = 0;
- while (bfs(capacities, s, f, parents, n)){
- int path_flow = INT_MAX;
- for (v = f; v != s; v = parents[v]){
- u = parents[v];
- path_flow = std::min(path_flow, capacities[u][v]);
- }
- for (v = f; v != s; v = parents[v]) {
- u = parents[v];
- capacities[u][v] -= path_flow;
- capacities[v][u] += path_flow;
- }
- max_flow += path_flow;
- }
- return max_flow;
- }
- int main() {
- #ifndef DEBUG
- std::ifstream in("maxflow.in");
- std::ofstream out("maxflow.out");
- #endif
- #ifdef DEBUG
- std::ifstream in("input.txt");
- std::ofstream out("output.txt");
- #endif
- int n, m;
- in >> n >> m;
- std::vector<std::vector<int> > adjacency_list(n, std::vector<int>(n, 0));
- for (int i = 0; i < m; i++) {
- int from, to, cost;
- in >> from >> to >> cost;
- adjacency_list[from - 1][to - 1] = cost;
- }
- out << edmonds_karp(adjacency_list, 0, n - 1, n);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement