SHARE
TWEET

Untitled

a guest Apr 25th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <queue>
  5. #include <random>
  6. #include <algorithm>
  7. #include<stack>
  8. #include <math.h>
  9.  
  10. const int INF = 2147483645;
  11.  
  12. class ListGraph {
  13. public:
  14.     ListGraph(int vertices_count);
  15.  
  16.     int VerticesCount() const;
  17.  
  18.     void AddEdge(int from, int to, int weight);
  19.  
  20.     void GetNextVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const;
  21.  
  22. private:
  23.     std::vector<std::vector<std::pair<int, int>>> adjacencyList;
  24. };
  25.  
  26. ListGraph::ListGraph(int vertices_count) {
  27.     adjacencyList.resize(vertices_count);
  28. }
  29.  
  30. int ListGraph::VerticesCount() const {
  31.     return adjacencyList.size();
  32. }
  33.  
  34. void ListGraph::AddEdge(int from, int to, int cap) {
  35.     adjacencyList[from].push_back(std::make_pair(to, cap));
  36. }
  37.  
  38. void ListGraph::GetNextVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const {
  39.     vertices = adjacencyList[vertex];
  40. }
  41.  
  42. bool BFS(ListGraph &graph, std::vector<std::vector<int>> &currflow, std::vector<int> &d) {
  43.     int N = graph.VerticesCount();
  44.     std::queue<int> q;
  45.     q.push(0);
  46.     d.assign(N,-1);
  47.     d[0] = 0;
  48.     while (!q.empty()) {
  49.         int curr = q.front();
  50.         q.pop();
  51.         std::vector<std::pair<int, int>> next;
  52.         graph.GetNextVertices(curr, next);
  53.         for (auto u : next) {
  54.             if (d[u.first] == -1 && currflow[curr][u.first] < u.second) {
  55.                 q.push(u.first);
  56.                 d[u.first] = d[curr] + 1;
  57.             }
  58.  
  59.         }
  60.     }
  61.     return d[N - 1] != -1;
  62. }
  63. int DFS(int v, int flow, ListGraph &graph, std::vector<int> &ptr, std::vector<std::vector<int>> &currflow,
  64.     std::vector<int> &d) {
  65.     int N = graph.VerticesCount();
  66.     if (v == N - 1 or !flow)
  67.         return flow;
  68.     std::vector<std::pair<int, int>> next;
  69.     graph.GetNextVertices(v, next);
  70.     for (; ptr[v] < next.size(); ++ptr[v]) {
  71.         int to = next[ptr[v]].first;
  72.         int curr_cup = next[ptr[v]].second;
  73.         if (d[to] != d[v] + 1)
  74.             continue;
  75.         int push = DFS(to, std::min(flow, curr_cup - currflow[v][to]), graph, ptr, currflow, d);
  76.         if (push != 0) {
  77.             currflow[v][to] += push;
  78.             currflow[to][v] -= push;
  79.             return push;
  80.         }
  81.  
  82.     }
  83.     return 0;
  84. }
  85.  
  86. int Find_max_flow(ListGraph &graph) {
  87.     int N = graph.VerticesCount();
  88.     int flow = 0;
  89.     std::vector<int> ptr(N, 0);
  90.     std::vector<int> d(N, -1);
  91.     std::vector<std::vector<int>> currflow(N, std::vector<int>(N, 0));
  92.  
  93.     while (true) {
  94.         if (!BFS(graph, currflow, d))
  95.             break;
  96.         ptr.assign(N, 0);
  97.         while (int pushed = DFS(0, INF, graph, ptr, currflow, d))
  98.             flow += pushed;
  99.  
  100.     }
  101.     return flow;
  102. }
  103.  
  104. int main() {
  105.     int N = 0, M = 0, from = 0, to = 0, cap = 0;
  106.     std::cin >> N >> M;
  107.     ListGraph graph(N);
  108.     for (int i = 0; i < M; ++i) {
  109.         std::cin >> from >> to >> cap;
  110.         graph.AddEdge(from - 1, to - 1, cap);
  111.     }
  112.     int ans = Find_max_flow(graph);
  113.     std::cout << ans;
  114.     return 0;
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top