Art_Uspen

Untitled

Sep 28th, 2021
697
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct Edge {
  6.     int from;
  7.     int to;
  8.     int capacity;
  9.     int flow;
  10.  
  11.     int other(int vertex) {
  12.         if (vertex == from) {
  13.             return to;
  14.         } else {
  15.             return from;
  16.         }
  17.     }
  18.     int capacity_to(int vertex) {
  19.         if (vertex == from) {
  20.             return flow;
  21.         } else {
  22.             return capacity - flow;
  23.         }
  24.     }
  25.     void add_flow_to(int vertex, int delta_flow) {
  26.         if (vertex == from) {
  27.             flow -= delta_flow;
  28.         } else {
  29.             flow += delta_flow;
  30.         }
  31.     }
  32. };
  33.  
  34. struct Graph {
  35.     vector<Edge> edges;
  36.     vector<vector<int>> graph;
  37.     vector<bool> used;
  38.     vector<int> previous_edge_index;
  39.  
  40.     Graph(int vertex_count) {
  41.         graph.resize(vertex_count);
  42.     }
  43.  
  44.     void add_edge(int from, int to, int capacity) {
  45.         edges.push_back({from, to, capacity, 0});
  46.         graph[from].push_back(edges.size() - 1);
  47.         graph[to].push_back(edges.size() - 1);
  48.     }
  49.  
  50.     void dfs(int v) {
  51.         used[v] = true;
  52.         for (int edge_index : graph[v]) {
  53.             int to = edges[edge_index].other(v);
  54.             if (!used[to] && edges[edge_index].capacity_to(to)) {
  55.                 previous_edge_index[to] = edge_index;
  56.                 dfs(to);
  57.             }
  58.         }
  59.  
  60.     }
  61.  
  62.     bool check_path(int source, int sink) {
  63.         used.assign(graph.size(), false);
  64.         previous_edge_index.assign(graph.size(), -1);
  65.         dfs(source);
  66.         return used[sink];
  67.     }
  68.     int get_bottle_neck(int source, int sink) {
  69.         int v = sink;
  70.         int res = 1e9;
  71.         while (v != source) {
  72.             int prev_e = previous_edge_index[v];
  73.             int prev_v = edges[prev_e].other(v);
  74.             res = min(res,edges[prev_e].capacity_to(v));
  75.             v = prev_v;
  76.         }
  77.         return res;
  78.     }
  79.     void add_flow(int source, int sink,int delta){
  80.         int v = sink;
  81.         while (v != source) {
  82.             int prev_e = previous_edge_index[v];
  83.             int prev_v = edges[prev_e].other(v);
  84.             edges[prev_e].add_flow_to(v,delta);
  85.             v = prev_v;
  86.         }
  87.     }
  88.  
  89.  
  90.     int max_flow(int source, int sink){
  91.         int res = 0;
  92.         while(check_path(source,sink)){
  93.             int bottle_n = get_bottle_neck(source,sink);
  94.             res += bottle_n;
  95.             add_flow(source,sink,bottle_n);
  96.         }
  97.         return res;
  98.     }
  99. };
RAW Paste Data