peltorator

!Диниц с Масштабированием

Jul 15th, 2017
171
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  6. #define in(s) freopen(s, "r", stdin)
  7. #define out(s) freopen(s, "w", stdout)
  8.  
  9. typedef long long ll;
  10. typedef long double ld;
  11.  
  12. struct edge
  13. {
  14.     int a, b, f, w;
  15. };
  16.  
  17. const int INF = 1e9 + 2;
  18. const int MAXN = 502;
  19.  
  20. int n, m;
  21. vector <edge> e;
  22. int arr[MAXN];
  23. vector <int> g[MAXN];
  24. ll ans = 0;
  25. int d[MAXN];
  26. int lowest;
  27.  
  28. void func(int s, int t, int w)
  29. {
  30.     g[s].push_back((int)e.size());
  31.     e.push_back({s, t, 0, w});
  32.  
  33.     g[t].push_back((int)e.size());
  34.     e.push_back({t, s, 0, 0});
  35. }
  36.  
  37. bool bfs()
  38. {
  39.     for (int i = 1; i <= n; i++)
  40.         d[i] = INF;
  41.     d[1] = 0;
  42.     queue<int> q;
  43.     q.push(1);
  44.     while (!q.empty() && d[n] == INF)
  45.     {
  46.         int v = q.front();
  47.         q.pop();
  48.         for (int i = 0; i < (int)g[v].size(); i++)
  49.         {
  50.             int id = g[v][i];
  51.             int u = e[id].b;
  52.             if (d[u] == INF && e[id].w - e[id].f >= lowest)
  53.             {
  54.                 d[u] = d[v] + 1;
  55.                 q.push(u);
  56.             }
  57.         }
  58.     }
  59.     return d[n] != INF;
  60. }
  61.  
  62. bool dfs(int v, int flow)
  63. {
  64.     if (!flow || v == n)
  65.         return flow;
  66.     for (; arr[v] < (int)g[v].size(); arr[v]++)
  67.     {
  68.         int id = g[v][arr[v]];
  69.         int u = e[id].b;
  70.         if (d[u] == d[v] + 1 && e[id].w - e[id].f >= flow)
  71.             if (dfs(u, flow))
  72.             {
  73.                 e[id].f += flow;
  74.                 e[id ^ 1].f -= flow;
  75.                 return flow;
  76.             }
  77.     }
  78.     return 0;
  79. }
  80.  
  81. int main()
  82. {
  83.     in("flow2.in");
  84.     out("flow2.out");
  85.     cin >> n >> m;
  86.     for (int i = 1; i <= m; i++)
  87.     {
  88.         int a, b, c;
  89.         cin >> a >> b >> c;
  90.         func(a, b, c);
  91.     }
  92.     for (lowest = (1 << 30); lowest >= 1;)
  93.     {
  94.         if (!bfs())
  95.         {
  96.             lowest >>= 1;
  97.             continue;
  98.         }
  99.         for (int i = 1; i <= n; i++)
  100.             arr[i] = 0;
  101.         while (dfs(1, lowest))
  102.             ans += lowest;
  103.     }
  104.     cout << ans << endl;
  105.     return 0;
  106. }
RAW Paste Data