Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <queue>
- #include <random>
- #include <algorithm>
- #include<stack>
- #include <math.h>
- const int INF = 2147483645;
- class ListGraph {
- public:
- ListGraph(int vertices_count);
- int VerticesCount() const;
- void AddEdge(int from, int to, int weight);
- void GetNextVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const;
- private:
- std::vector<std::vector<std::pair<int, int>>> adjacencyList;
- };
- ListGraph::ListGraph(int vertices_count) {
- adjacencyList.resize(vertices_count);
- }
- int ListGraph::VerticesCount() const {
- return adjacencyList.size();
- }
- void ListGraph::AddEdge(int from, int to, int cap) {
- adjacencyList[from].push_back(std::make_pair(to, cap));
- }
- void ListGraph::GetNextVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const {
- vertices = adjacencyList[vertex];
- }
- bool BFS(ListGraph &graph, std::vector<std::vector<int>> &currflow, std::vector<int> &d) {
- int N = graph.VerticesCount();
- std::queue<int> q;
- q.push(0);
- d.assign(N,-1);
- d[0] = 0;
- while (!q.empty()) {
- int curr = q.front();
- q.pop();
- std::vector<std::pair<int, int>> next;
- graph.GetNextVertices(curr, next);
- for (auto u : next) {
- if (d[u.first] == -1 && currflow[curr][u.first] < u.second) {
- q.push(u.first);
- d[u.first] = d[curr] + 1;
- }
- }
- }
- return d[N - 1] != -1;
- }
- int DFS(int v, int flow, ListGraph &graph, std::vector<int> &ptr, std::vector<std::vector<int>> &currflow,
- std::vector<int> &d) {
- int N = graph.VerticesCount();
- if (v == N - 1 or !flow)
- return flow;
- std::vector<std::pair<int, int>> next;
- graph.GetNextVertices(v, next);
- for (; ptr[v] < next.size(); ++ptr[v]) {
- int to = next[ptr[v]].first;
- int curr_cup = next[ptr[v]].second;
- if (d[to] != d[v] + 1)
- continue;
- int push = DFS(to, std::min(flow, curr_cup - currflow[v][to]), graph, ptr, currflow, d);
- if (push != 0) {
- currflow[v][to] += push;
- currflow[to][v] -= push;
- return push;
- }
- }
- return 0;
- }
- int Find_max_flow(ListGraph &graph) {
- int N = graph.VerticesCount();
- int flow = 0;
- std::vector<int> ptr(N, 0);
- std::vector<int> d(N, -1);
- std::vector<std::vector<int>> currflow(N, std::vector<int>(N, 0));
- while (true) {
- if (!BFS(graph, currflow, d))
- break;
- ptr.assign(N, 0);
- while (int pushed = DFS(0, INF, graph, ptr, currflow, d))
- flow += pushed;
- }
- return flow;
- }
- int main() {
- int N = 0, M = 0, from = 0, to = 0, cap = 0;
- std::cin >> N >> M;
- ListGraph graph(N);
- for (int i = 0; i < M; ++i) {
- std::cin >> from >> to >> cap;
- graph.AddEdge(from - 1, to - 1, cap);
- }
- int ans = Find_max_flow(graph);
- std::cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement