fork download
copy 
  1. #pragma GCC optimize(3)
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. const int MAXN = 5005;
  8.  
  9. template <int MAXN, class T = int> struct HLPP {
  10.     const T INF = numeric_limits<T>::max();
  11.     struct edge {
  12.         int to, rev;
  13.         T f;
  14.     };
  15.     int s = MAXN - 1, t = MAXN - 2;
  16.     vector<edge> adj[MAXN];
  17.     vector<int> lst[MAXN], gap[MAXN];
  18.     T excess[MAXN];
  19.     int highest, height[MAXN], cnt[MAXN], work;
  20.     void addEdge(int from, int to, T f, bool isDirected = true) {
  21.         adj[from].push_back({to, adj[to].size(), f});
  22.         adj[to].push_back({from, adj[from].size() - 1, isDirected ? 0 : f});
  23.     }
  24.     void updHeight(int v, int nh) {
  25.         work++;
  26.         if (height[v] != MAXN)
  27.             cnt[height[v]]--;
  28.         height[v] = nh;
  29.         if (nh == MAXN)
  30.             return;
  31.         cnt[nh]++, highest = nh;
  32.         gap[nh].push_back(v);
  33.         if (excess[v] > 0)
  34.             lst[nh].push_back(v);
  35.     }
  36.     void globalRelabel() {
  37.         work = 0;
  38.         fill(height, height + MAXN, MAXN);
  39.         fill(cnt, cnt + MAXN, 0);
  40.         for (int i = 0; i < highest; i++)
  41.             lst[i].clear(), gap[i].clear();
  42.         height[t] = 0;
  43.         queue<int> q({t});
  44.         while (!q.empty()) {
  45.             int v = q.front();
  46.             q.pop();
  47.             for (auto &e : adj[v])
  48.                 if (height[e.to] == MAXN && adj[e.to][e.rev].f > 0)
  49.                     q.push(e.to), updHeight(e.to, height[v] + 1);
  50.             highest = height[v];
  51.         }
  52.     }
  53.     void push(int v, edge &e) {
  54.         if (excess[e.to] == 0)
  55.             lst[height[e.to]].push_back(e.to);
  56.         T df = min(excess[v], e.f);
  57.         e.f -= df, adj[e.to][e.rev].f += df;
  58.         excess[v] -= df, excess[e.to] += df;
  59.     }
  60.     void discharge(int v) {
  61.         int nh = MAXN;
  62.         for (auto &e : adj[v]) {
  63.             if (e.f > 0) {
  64.                 if (height[v] == height[e.to] + 1) {
  65.                     push(v, e);
  66.                     if (excess[v] <= 0)
  67.                         return;
  68.                 } else
  69.                     nh = min(nh, height[e.to] + 1);
  70.             }
  71.         }
  72.         if (cnt[height[v]] > 1)
  73.             updHeight(v, nh);
  74.         else {
  75.             for (int i = height[v]; i <= highest; i++) {
  76.                 for (auto j : gap[i])
  77.                     updHeight(j, MAXN);
  78.                 gap[i].clear();
  79.             }
  80.         }
  81.     }
  82.     T calc(int heur_n = MAXN) {
  83.         fill(begin(excess), end(excess), 0);
  84.         excess[s] = INF, excess[t] = -INF;
  85.         globalRelabel();
  86.         for (auto &e : adj[s])
  87.             push(s, e);
  88.         for (; highest >= 0; highest--) {
  89.             while (!lst[highest].empty()) {
  90.                 int v = lst[highest].back();
  91.                 lst[highest].pop_back();
  92.                 discharge(v);
  93.                 if (work > 4 * heur_n)
  94.                     globalRelabel();
  95.             }
  96.         }
  97.         return excess[t] + INF;
  98.     }
  99. };
  100. void read_uint() {}
  101. template <class T, class... S> inline void read_uint(T &a, S &... b) {
  102.     static char c;
  103.     while (isspace(c = getchar_unlocked()))
  104.         ;
  105.     for (a = c - '0'; isdigit(c = getchar_unlocked()); a = a * 10 + c - '0')
  106.         ;
  107.     read_uint(b...);
  108. }
  109. HLPP<MAXN, ll> hlpp;
  110. signed main() {
  111.     ios::sync_with_stdio(0);
  112.     cin.tie(0);
  113.     int n, m, p;
  114.     read_uint(n, m);
  115.     int s = 1, t = n;
  116.     // read_uint(s), read_uint(t);
  117.     for (int i = 0, u, v, f; i < m; ++i) {
  118.         read_uint(u), read_uint(v), read_uint(f);
  119.         hlpp.addEdge(u, v, f, false);
  120.     }
  121.     hlpp.s = s, hlpp.t = t;
  122.     ll ans = hlpp.calc(n);
  123.     cout << ans << endl;
  124.     return 0;
  125.     // vector<array<int, 3>> res;
  126.     // for (int i = 0; i < MAXN; i++) {
  127.     //     for (auto j : hlpp.adj[i]) {
  128.     //         if (j.f < j.orig)
  129.     //             res.push_back({i, j.to, j.orig - j.f});
  130.     //     }
  131.     //     // if (hlpp.adj[i].size())
  132.     //     //     cout << endl;
  133.     // }
  134.     // cout << n << ' ' << ans << ' ' << res.size() << endl;
  135.     // for (auto i : res) {
  136.     //     cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
  137.     // }
  138. }
  139.  
Runtime error #stdin #stdout 0s 15672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/j7H5nD
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!