peltorator

!mincost Форд-Беллман (spfa)

May 5th, 2019
162
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. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  12.  
  13. typedef long long ll;
  14.  
  15. struct Edge
  16. {
  17.     int from, to;
  18.     ll c, f, w;
  19.     Edge(int from, int to, ll c, ll f, ll w):
  20.         from(from),
  21.         to(to),
  22.         c(c),
  23.         f(f),
  24.         w(w) {}
  25. };
  26.  
  27. const int N = 100005;
  28. const ll INF = 1e18 + 239;
  29. vector<Edge> e;
  30. vector<int> g[N];
  31. int used[N], pr[N], t;
  32. ll d[N];
  33.  
  34.  
  35. void upd(int ind, int f)
  36. {
  37.     e[ind].f += f;
  38.     e[ind ^ 1].f -= f;
  39. }
  40.  
  41. ll cost;
  42.  
  43. int solve()
  44. {
  45.     int n;
  46.     if (!(cin >> n))
  47.         return 1;
  48.     int m, s;
  49.     cin >> m;
  50.     s = 0;
  51.     t = n - 1;
  52.     e.clear();
  53.     for (int i = 0; i < n; i++)
  54.         g[i].clear();
  55.     for (int i = 0; i < m; i++)
  56.     {
  57.         int x, y, z, q;
  58.         cin >> x >> y >> z >> q;
  59.         x--;
  60.         y--;
  61.         g[x].push_back(sz(e));
  62.         e.push_back(Edge(x, y, z, 0, q));
  63.         g[y].push_back(sz(e));
  64.         e.push_back(Edge(y, x, 0, 0, -q));
  65.     }
  66.     cost = 0;
  67.     while (true)
  68.     {
  69.         for (int i = 0; i < n; i++)
  70.             d[i] = INF, used[i] = 0;
  71.         d[s] = 0;
  72.         queue<int> q;
  73.         q.push(s);
  74.         used[s] = 1;
  75.         while (sz(q))
  76.         {
  77.             int v = q.front();
  78.             q.pop();
  79.             used[v] = 0;
  80.             for (int ind : g[v])
  81.             {
  82.                 if (e[ind].f < e[ind].c && d[e[ind].to] > d[v] + e[ind].w)
  83.                 {
  84.                     d[e[ind].to] = d[v] + e[ind].w;
  85.                     pr[e[ind].to] = ind;
  86.                     if (!used[e[ind].to])
  87.                     {
  88.                         used[e[ind].to] = 1;
  89.                         q.push(e[ind].to);
  90.                     }
  91.                 }
  92.             }
  93.         }
  94.         if (!used[t])
  95.             break;
  96.         int v = t;
  97.         ll mn = INF;
  98.         ll sum = 0;
  99.         while (v != s)
  100.         {
  101.             sum += e[pr[v]].w;
  102.             mn = min(mn, e[pr[v]].c - e[pr[v]].f);
  103.             v = e[pr[v]].from;
  104.         }
  105.         cost += sum * mn;
  106.         v = t;
  107.         while (v != s)
  108.         {
  109.             upd(pr[v], mn);
  110.             v = e[pr[v]].from;
  111.         }
  112.     }
  113.     cout << cost << endl;
  114.     return 0;
  115. }
  116.  
  117. int32_t main()
  118. {
  119.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  120.     int TET = 1e9;
  121.     //cin >> TET;
  122.     while (TET--)
  123.     {
  124.         if (solve())
  125.             break;
  126.         #ifdef ONPC
  127.             cout << "\n__________________________" << endl;
  128.         #endif
  129.     }
  130.     #ifdef ONPC
  131.         cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  132.     #endif
  133. }
  134. close
RAW Paste Data