Shiyan12

Untitled

May 11th, 2021
574
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int n, m;
  9. vector <vector <int>> g;
  10.  
  11. bool bfs(vector <vector <int>> rg, int s, int& t, vector <int>& parent) {
  12.     vector <bool> visited(n);
  13.     queue <int> q;
  14.     q.push(s);
  15.     visited[s] = true;
  16.     parent[s] = -1;
  17.     while (!q.empty()) {
  18.         int u = q.front();
  19.         q.pop();
  20.         for (int v = 0; v < n; v++) {
  21.             if (!visited[v] && rg[u][v] > 0) {
  22.                 parent[v] = u;
  23.                 if (v == t) {
  24.                     return true;
  25.                 }
  26.                 q.push(v);
  27.                 visited[v] = true;
  28.             }
  29.         }
  30.     }
  31.     return false;
  32. }
  33.  
  34. int ford_fulkerson(vector <vector <int>> g, int s, int t) {
  35.     int u, v;
  36.     vector <vector <int>> rg(n);
  37.     for (u = 0; u < n; u++) {
  38.         rg[u].resize(n);
  39.         for (v = 0; v < n; v++)
  40.             rg[u][v] = g[u][v];
  41.     }
  42.     vector <int> parent(n);
  43.     int max_flow = 0;
  44.     while (bfs(rg, s, t, parent)) {
  45.         int path_flow = INT_MAX;
  46.         for (v = t; v != s; v = parent[v]) {
  47.             u = parent[v];
  48.             path_flow = min(path_flow, rg[u][v]);
  49.         }
  50.         for (v = t; v != s; v = parent[v]) {
  51.             u = parent[v];
  52.             rg[u][v] -= path_flow;
  53.             rg[v][u] += path_flow;
  54.         }
  55.         max_flow += path_flow;
  56.     }
  57.     return max_flow;
  58. }
  59.  
  60. int main() {
  61.     setlocale(LC_ALL, "rus");
  62.  
  63.     ifstream rd;
  64.     rd.open("graph.txt");
  65.  
  66.     rd >> n >> m;
  67.  
  68.     g.resize(n);
  69.     for (int i = 0; i < n; i++)
  70.         g[i].resize(n, 0);
  71.    
  72.     for (int i = 0; i < m; i++) {
  73.         int u, v, w;
  74.         rd >> u >> v >> w;
  75.         g[u][v] = w;
  76.     }
  77.  
  78.     cout << "Максимальный поток: " << ford_fulkerson(g, 0, n - 1) << endl;
  79.    
  80.     system("pause");
  81.     return 0;
  82. }
RAW Paste Data