Advertisement
Khody

Untitled

Feb 28th, 2020
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <iomanip>
  5. #include <random>
  6. #include <ctime>
  7. #include <bitset>
  8. #include <map>
  9. #include <set>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. #include <cmath>
  13. #include <climits>
  14. #include <cstring>
  15. #include <queue>
  16. #include <deque>
  17. #include <list>
  18. #include <stack>
  19.  
  20. #define pb push_back
  21. #define ff first
  22. #define ss second
  23. #define sqr(x) (x) * (x)
  24. #define cb(x) (x) * (x) * (x)
  25. #define SIZE 101
  26. #define INF 1e18 + 9
  27.  
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32. typedef long double ld;
  33. typedef pair<int, int> pii;
  34. typedef pair<ll, ll> pll;
  35.  
  36. const int inf = 2e9;
  37. const ll linf = 2e18;
  38. const ll mod = 1e9 + 7;
  39.  
  40. template <typename T>
  41. ostream& operator << (ostream& s, vector<T>& v) {
  42.     for (auto el : v) {
  43.         s << el << " ";
  44.     }
  45.     return s;
  46. }
  47.  
  48. typedef vector<int> graf_line;
  49. typedef vector<graf_line> graf;
  50.  
  51. typedef vector<int> vint;
  52. typedef vector<vint> vvint;
  53.  
  54.  
  55. int main() {
  56.  
  57.     int n;
  58.     cin >> n;
  59.     vvint c(n, vint(n));
  60.     for (int i = 0; i < n; i++)
  61.         for (int j = 0; j < n; j++){
  62.             if (j > i) c[i][j] = j - i;
  63.  
  64.         }
  65.     vvint f(n, vint(n));
  66.     for (;;)
  67.     {
  68.  
  69.         vint from(n, -1);
  70.         vint q(n);
  71.         int h = 0, t = 0;
  72.         q[t++] = 0;
  73.         from[0] = 0;
  74.         for (int cur; h < t;)
  75.         {
  76.             cur = q[h++];
  77.             for (int v = 0; v < n; v++)
  78.                 if (from[v] == -1 &&
  79.                     c[cur][v] - f[cur][v] > 0)
  80.                 {
  81.                     q[t++] = v;
  82.                     from[v] = cur;
  83.                 }
  84.         }
  85.  
  86.         if (from[n - 1] == -1)
  87.             break;
  88.         int cf = inf;
  89.         for (int cur = n - 1; cur != 0; )
  90.         {
  91.             int prev = from[cur];
  92.             cf = min(cf, c[prev][cur] - f[prev][cur]);
  93.             cur = prev;
  94.         }
  95.  
  96.         for (int cur = n - 1; cur != 0; )
  97.         {
  98.             int prev = from[cur];
  99.             f[prev][cur] += cf;
  100.             f[cur][prev] -= cf;
  101.             cur = prev;
  102.         }
  103.  
  104.     }
  105.  
  106.     int flow = 0;
  107.     for (int i = 0; i < n; i++)
  108.         if (c[0][i])
  109.             flow += f[0][i];
  110.  
  111.     cout << flow;
  112.  
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement