SHARE
TWEET

Untitled

a guest Jun 24th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2. #include <string>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. struct NODE
  11. {
  12.     int h;
  13.     int e;
  14.     vector<int> f;
  15.     vector<int> c;
  16.     vector<int> inc;
  17. };
  18.  
  19. class FLOW
  20. {
  21.     std::vector<NODE> arr;
  22.     std::vector<char> name;
  23.     std::vector<int> extra;
  24.     int start = -1;
  25.     int finish = -1;
  26.     void push(int, int);
  27.     void relabel(int);
  28.     void init();
  29.     bool discharge(int);
  30.     /*int leveldiff(int);
  31.     void isextra(int);*/
  32. public:
  33.     void input(fstream&);
  34.     int calc_maxflow();
  35. };
  36.  
  37. bool FLOW :: discharge(int u)
  38. {
  39.     bool lifted = false;
  40.     while (arr[u].e > 0)
  41.     {
  42.         int i;
  43.         for (i = 0; i < arr[u].inc.size() && arr[u].e > 0; ++i)
  44.         {
  45.             if (arr[u].h == arr[arr[u].inc[i]].h + 1 && arr[u].c > arr[u].f)
  46.             {
  47.                 push(u, arr[u].inc[i]);
  48.             }
  49.         }
  50.         if (i == arr[u].inc.size() && arr[u].e > 0)
  51.         {
  52.             relabel(u);
  53.             lifted = true;
  54.         }
  55.     }
  56.     extra.erase(std::remove(extra.begin(), extra.end(), u), extra.end());
  57.     return lifted;
  58. }
  59.  
  60. //void FLOW::isextra(int u)
  61. //{
  62. //  bool flaq = false;
  63. //  for (int i = 0; i < arr[u].c.size(); ++i)
  64. //  {
  65. //      if (arr[u].c != arr[u].f)
  66. //      {
  67. //          flaq = true;
  68. //          break;
  69. //      }
  70. //  }
  71. //  if (!flaq)
  72. //      extra.erase(std::remove(extra.begin(), extra.end(), u), extra.end());
  73. //}
  74.  
  75. //int FLOW::leveldiff(int u)
  76. //{
  77. //  for (int i = 0; i < arr[u].inc.size(); ++i)
  78. //  {
  79. //      if (arr[u].h > arr[arr[u].inc[i]].h && arr[u].c[i] != arr[u].f[i])
  80. //          return arr[u].inc[i];
  81. //  }
  82. //  return -1;
  83. //}
  84.  
  85. void FLOW::push(int u, int v)
  86. {
  87.     int num = 0;
  88.     for (int i = 0; i < arr[u].inc.size(); ++i)
  89.     {
  90.         if (arr[u].inc[i] == v)
  91.         {
  92.             num = i;
  93.             break;
  94.         }
  95.     }
  96.     int d = ((arr[u].c[num] - arr[u].f[num]) < arr[u].e) ? (arr[u].c[num] - arr[u].f[num]) : arr[u].e;
  97.     arr[u].e -= d;
  98.     if (!arr[u].e)
  99.         extra.erase(std::remove(extra.begin(), extra.end(), u), extra.end());
  100.     arr[u].f[num] += d;
  101.     arr[v].e += d;
  102.     if (arr[v].e && v != finish && v != start && !count(extra.begin(), extra.end(), v))
  103.         extra.push_back(v);
  104. }
  105.  
  106. void FLOW::relabel(int u)
  107. {
  108.     int min = arr.size() * 2;
  109.     for (int i = 0; i < arr[u].inc.size(); ++i)
  110.     {
  111.         if (arr[arr[u].inc[i]].h < min && arr[u].f[i] != arr[u].c[i])
  112.             min = arr[arr[u].inc[i]].h;
  113.     }
  114.     arr[u].h = min + 1;
  115. }
  116.  
  117. void FLOW::init()
  118. {
  119.     for (int i = 0; i < arr.size(); ++i)
  120.     {
  121.         if (i == start)
  122.         {
  123.             arr[i].h = arr.size();
  124.             for (int j = 0; j < arr[i].inc.size(); ++j)
  125.             {
  126.                 arr[arr[i].inc[j]].e = arr[i].c[j];
  127.                 arr[i].f[j] = arr[i].c[j];
  128.                 if (arr[i].inc[j] != start && arr[i].inc[j] != finish)
  129.                     extra.push_back(arr[i].inc[j]);
  130.             }
  131.         }
  132.         else
  133.         {
  134.             arr[i].h = 0;
  135.         }
  136.     }
  137. }
  138.  
  139. int FLOW::calc_maxflow()
  140. {
  141.     if (start == -1 || finish == -1)
  142.     {
  143.         cout << "Error! Incorrect input data.\n";
  144.         return -1;
  145.     }
  146.     else
  147.     {
  148.         init();
  149.         while (extra.size())
  150.         {
  151.             discharge(extra[0]);
  152.         }
  153.         return arr[finish].e;
  154.     }
  155. }
  156.  
  157. void FLOW::input(fstream & file)
  158. {
  159.     while (!file.eof())
  160.     {
  161.         bool flaq = false;
  162.         int first, second;
  163.         string str1, str2, str3;
  164.         std::getline(file, str1, ' ');
  165.         for (int i = 0; i < name.size(); ++i)
  166.         {
  167.             if (name[i] == str1[0])
  168.             {
  169.                 flaq = true;
  170.                 first = i;
  171.             }
  172.         }
  173.         if (!flaq)
  174.         {
  175.             if (str1[0] == 'S')
  176.                 start = name.size();
  177.             first = name.size();
  178.             name.push_back(str1[0]);
  179.             arr.push_back(NODE());
  180.         }
  181.         flaq = false;
  182.         std::getline(file, str2, ' ');
  183.         for (int i = 0; i < name.size(); ++i)
  184.         {
  185.             if (name[i] == str2[0])
  186.             {
  187.                 flaq = true;
  188.                 second = i;
  189.             }
  190.         }
  191.         if (!flaq)
  192.         {
  193.             if (str2[0] == 'T')
  194.                 finish = name.size();
  195.             second = name.size();
  196.             name.push_back(str2[0]);
  197.             arr.push_back(NODE());
  198.         }
  199.         std::getline(file, str3, '\n');
  200.         arr[first].inc.push_back(second);
  201.         arr[first].c.push_back(stoi(str3));
  202.         arr[second].inc.push_back(first);
  203.         arr[second].c.push_back(stoi(str3));
  204.         arr[first].f.push_back(0);
  205.         arr[second].f.push_back(0);
  206.     }
  207. }
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