peltorator

!min-cost max flow

Jul 7th, 2017
149
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define fastRead ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  4. #define in(s) freopen(s, "r", stdin)
  5. #define out(s) freopen(s, "w", stdout)
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. const int MAXN = 1000;
  12.  
  13. vector<ll> g[MAXN], c[MAXN], f[MAXN], lvl, p, used, rev[MAXN], pr;
  14. vector<ll> cost[MAXN], d;
  15.  
  16. void func(int k, int l, int w, int cost1, int t)
  17. {
  18.     g[k].push_back(l);
  19.     f[k].push_back(0);
  20.     c[k].push_back(w);
  21.     rev[k].push_back(t);
  22.     cost[k].push_back(cost1);
  23. }
  24.  
  25. void fu(int k, int l, int w, int cost1)
  26. {
  27.     func(k, l, w, cost1, (int)g[l].size());
  28.     func(l, k, 0, -cost1, (int)g[k].size() - 1);
  29. }
  30.  
  31. int main()
  32. {
  33.     assert(in("mincost.in"));
  34.     assert(out("mincost.out"));
  35.     int n, m;
  36.     cin >> n >> m;
  37.     for (int i = 1; i <= m; i++)
  38.     {
  39.         int k, l, w, cost1;
  40.         scanf("%d %d %d %d", &k, &l, &w, &cost1);
  41.         fu(k, l, w, cost1);
  42.     }
  43.     ll res = 0;
  44.     while (true)
  45.     {
  46.         d.assign(n + 1, 1e16);
  47.         used.assign(n + 1, 0);
  48.         p.assign(n + 1, -1);
  49.         pr.assign(n + 1, -1);
  50.         d[1] = 0;
  51.         for (int i = 0; i <= n + 1; i++)
  52.             for (int v = 1; v <= n; v++)
  53.                 for (int j = 0; j < (int)g[v].size(); j++)
  54.                     if (c[v][j] > f[v][j] && d[g[v][j]] > d[v] + cost[v][j])
  55.                     {
  56.                         d[g[v][j]] = d[v] + cost[v][j];
  57.                         p[g[v][j]] = v;
  58.                         pr[g[v][j]] = j;
  59.                     }
  60.         if (p[n] == -1)
  61.             break;
  62.         ll ans = c[p[n]][pr[n]] - f[p[n]][pr[n]];
  63.         int v = p[n];;
  64.         while (v != 1)
  65.         {
  66.             ans = min(ans, 1LL * c[p[v]][pr[v]] - f[p[v]][pr[v]]);
  67.             v = p[v];
  68.         }
  69.         v = n;
  70.         while (v != 1)
  71.         {
  72.             res += cost[p[v]][pr[v]] * ans;
  73.             f[p[v]][pr[v]] += ans;
  74.             f[v][rev[p[v]][pr[v]]] -= ans;
  75.             v = p[v];
  76.         }
  77.     }
  78.     cout << res;
  79.     return 0;
  80. }
RAW Paste Data