peltorator

!Форд-Фалкерсон

Apr 19th, 2019
184
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifdef ONPC
  2.     # define _GLIBCXX_DEBUG
  3.     #define deb(a) cerr << "========" << #a << " = " << a << endl;
  4. #else
  5.     #define deb(a)
  6. #endif
  7. #define sz(a) (int)(a).size()
  8.  
  9.  
  10. #include <bits/stdc++.h>
  11.  
  12. using namespace std;
  13. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  14.  
  15. typedef long long ll;
  16.  
  17. struct Edge
  18. {
  19.     int from, to, c, f;
  20.     Edge(int from, int to, int c, int f):
  21.         from(from),
  22.         to(to),
  23.         c(c),
  24.         f(f) {}
  25. };
  26.  
  27. const int N = 100005;
  28. const int INF = 1e9 + 7;
  29. vector<Edge> e;
  30. vector<int> g[N];
  31. int used[N], t;
  32.  
  33.  
  34. void upd(int ind, int f)
  35. {
  36.     e[ind].f += f;
  37.     e[ind ^ 1].f -= f;
  38. }
  39.  
  40. int dfs(int v, int cur)
  41. {
  42.     if (v == t)
  43.         return cur;
  44.     used[v] = 1;
  45.     for (int ind : g[v])
  46.     {
  47.         int u = e[ind].to, f = e[ind].f, c = e[ind].c;
  48.         if (!used[u] && f < c)
  49.         {
  50.             int len = dfs(u, min(cur, c - f));
  51.             if (len)
  52.             {
  53.                 upd(ind, len);
  54.                 return len;
  55.             }
  56.         }
  57.     }
  58.     return 0;
  59. }
  60.  
  61. int solve()
  62. {
  63.     int n;
  64.     if (!(cin >> n))
  65.         return 1;
  66.     int m, s;
  67.     cin >> m;
  68.     s = 0;
  69.     t = n - 1;
  70.     e.clear();
  71.     for (int i = 0; i < n; i++)
  72.         g[i].clear();
  73.     for (int i = 0; i < m; i++)
  74.     {
  75.         int x, y, z;
  76.         cin >> x >> y >> z;
  77.         x--;
  78.         y--;
  79.         g[x].push_back(sz(e));
  80.         e.push_back(Edge(x, y, z, 0));
  81.         g[y].push_back(sz(e));
  82.         e.push_back(Edge(y, x, 0, 0));
  83.         g[y].push_back(sz(e));
  84.         e.push_back(Edge(y, x, z, 0));
  85.         g[x].push_back(sz(e));
  86.         e.push_back(Edge(x, y, 0, 0));
  87.     }
  88.     int flow = 0;
  89.     while (true)
  90.     {
  91.         for (int i = 0; i < n; i++)
  92.             used[i] = 0;
  93.         int x = dfs(s, INF);
  94.         if (x)
  95.             flow += x;
  96.         else
  97.             break;
  98.     }
  99.     cout << flow << endl;
  100.     for (int i = 0; i < sz(e); i += 4)
  101.         cout << e[i].f - e[i + 2].f << ' ';
  102.     cout << endl;
  103.     return 1;
  104. }
  105.  
  106. int32_t main()
  107. {
  108.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  109.     int TET = 1e9;
  110.     //cin >> TET;
  111.     while (TET--)
  112.     {
  113.         if (solve())
  114.             break;
  115.         #ifdef ONPC
  116.             cout << "\n__________________________" << endl;
  117.         #endif
  118.     }
  119.     #ifdef ONPC
  120.         cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  121.     #endif
  122.     return 0;
  123. }
RAW Paste Data