test/aoj/min_cost_flow.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_B

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_B"
#include "include/mtl/min_cost_flow.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int V,E,F; cin>>V>>E>>F;
  MinCostFlowGraph<int> mcfg(V);
  for (int i = 0; i < E; i++) {
    int u,v,c,d; cin>>u>>v>>c>>d;
    mcfg.add_edge(u, v, c, d);
  }
  auto res = mcfg.flow(0, V-1, F);
  cout << (res.first == F ? res.second : -1) << endl;
}

#line 1 "test/aoj/min_cost_flow.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_B"
#line 2 "include/mtl/min_cost_flow.hpp"
#include <vector>
#include <limits>
#line 2 "include/mtl/fibonacci_heap.hpp"
#include <memory>
#include <cassert>
#line 5 "include/mtl/fibonacci_heap.hpp"
#include <array>
#include <list>
#include <iostream>

template<typename T, typename Cond = std::less<>>
class FibonacciHeap {
  Cond cond_;

 public:
  struct Node;
  using node_ptr = Node*;
  using const_node_ptr = const Node*;
  struct Node {
    node_ptr next = nullptr;
    node_ptr prev = nullptr;
    node_ptr child = nullptr;
    node_ptr parent = nullptr;
    int deg = 0;
    bool marked = false;
    bool enabled = false;
    std::pair<int, T> value;

    Node() = default;
    void init(int k, T v) {
      next = prev = this;
      child = parent = nullptr;
      deg = 0;
      marked = false;
      enabled = true;
      value = {k, v};
    }
    T priority() const { return value.second; }
    void free() {
      enabled = false;
    }
  };

 private:
  node_ptr root_ = nullptr;
  size_t sz_ = 0;
  std::vector<node_ptr> map_;
  std::vector<Node> container_;
  std::vector<node_ptr> deg_table_;

 public:
  explicit FibonacciHeap(size_t size) : map_(size) {
    container_.reserve(size);
    std::array<size_t,2> tb{1,1};
    int k = 2;
    while (tb[1] < size) {
      auto x = tb[0]+tb[1];
      tb[0] = tb[1];
      tb[1] = x;
      ++k;
    }
    deg_table_.resize(k);
  }

  inline std::pair<int, T> top() const {
    assert(root_ and root_->enabled);
    return root_->value;
  }

  inline std::pair<int, T> get(int key) const {
    assert(map_[key] and map_[key]->enabled);
    return map_[key]->value;
  }

  // Time complexity: O(1)
  void push(int key, T value) {
    if (map_[key] and map_[key]->enabled) {
      update(key, value);
      return;
    }
    if (!map_[key]) {
      container_.emplace_back();
      map_[key] = &container_.back();
    }
    node_ptr node = map_[key];
    node->init(key, value);
    _PushLink(node, &deg_table_[0]);
    if (!root_ or _CompareNodePriority(root_, node))
      root_ = node;
    ++sz_;
  }

  // Time complexity: O(log n)
  void update(int key, T updated_value) {
    if (!map_[key] or !map_[key]->enabled) {
      push(key, updated_value);
      return;
    }
    auto node = map_[key];
    if (!cond_(node->priority(), updated_value)) {
      return;
    }
    node->value.second = updated_value;
    if (node->parent and _CompareNodePriority(node->parent, node)) {
      _Consolidate(node);
    }
    assert(root_);
    if (_CompareNodePriority(root_, node)) {
      root_ = node;
    }
  }

  // Time complexity: O(log n)
  void pop() {
    assert(root_);
    auto r = root_;
    root_ = nullptr;
    _PopLink(r, &deg_table_[r->deg]);
    _ExpandChildren(r);
    _ExtractTop();
    r->free();
    --sz_;
  }

  // Time complexity: O(log n)
  void erase(int key) {
    assert(map_[key] and map_[key]->enabled);
    auto node = map_[key];
    bool needs_extraction = root_ == node;
    if (node->parent) {
      _Consolidate(node);
    }
    assert(!node->parent);
    _PopLink(node, &deg_table_[node->deg]);
    _ExpandChildren(node);
    if (needs_extraction)
      _ExtractTop();
    node->free();
    --sz_;
  }

  size_t size() const { return sz_; }
  bool empty() const { return size() == 0; }
  void clear() {
    root_ = nullptr;
    sz_ = 0;
    map_.fill(nullptr);
    container_.clear();
  }

  void print_for_debug() const {
      for (int k = 0; k < (int)deg_table_.size(); k++) {
        std::cout<<"d="<<k<<std::endl;
        if (deg_table_[k]) {
          std::cout<<"forward"<<std::endl;
          auto r = deg_table_[k];
          do {
            std::cout << r->priority() << ' ' << std::flush;
            r = r->next;
          } while (r != deg_table_[k]);
          std::cout<<std::endl;
          std::cout<<"deg"<<std::endl;
          r = deg_table_[k];
          do {
            std::cout<<r->deg<<' '<<std::flush;
            r = r->prev;
          } while (r != deg_table_[k]);
          std::cout<<std::endl;
        } else {
          std::cout<<"empty"<<std::endl;
        }
      }
  }

 private:
  bool _CompareNodePriority(const_node_ptr l, const_node_ptr r) const {
    return cond_(l->priority(), r->priority());
  }

  void _PushLink(node_ptr node, node_ptr* link_head) {
    if (!*link_head) {
      *link_head = node;
      node->next = node;
      node->prev = node;
    } else {
      auto b = (*link_head)->prev;
      node->next = *link_head;
      node->prev = b;
      b->next = node;
      (*link_head)->prev = node;
    }
  }

  void _PopLink(node_ptr node, node_ptr* link_head) {
    assert(*link_head);
    if (node->next == node) {
      assert(node->prev == node);
      assert(*link_head == node);
      *link_head = nullptr;
    } else {
      auto n = node->next;
      auto p = node->prev;
      p->next = n;
      n->prev = p;
      if (*link_head == node)
        *link_head = n;
      node->next = node;
      node->prev = node;
    }
  }

  node_ptr _Meld(node_ptr l, node_ptr r) {
    assert(l->deg == r->deg);
    if (_CompareNodePriority(l, r)) {
      std::swap(l, r);
    }
    _PushLink(r, &l->child);
    r->parent = l;
    l->deg++;
    return l;
  }

  void _ExpandChildren(node_ptr node) {
    while (node->child) {
      auto c = node->child;
      _PopLink(c, &node->child);
      --node->deg;
      c->parent = nullptr;
      c->marked = false;
      _PushLink(c, &deg_table_[c->deg]);
    }
    assert(node->deg == 0);
  }

  void _ExtractTop() {
    int k = 0;
    while (k < (int)deg_table_.size()) {
      while (k < (int)deg_table_.size() and !deg_table_[k]) ++k;
      if (k == (int)deg_table_.size())
        break;
      if (deg_table_[k]->next != deg_table_[k]) { // Multiple trees at current degree
        auto node = deg_table_[k];
        _PopLink(node, &deg_table_[k]);
        assert(node->deg == k);
        while (deg_table_[node->deg]) {
          auto d = node->deg;
          auto u = deg_table_[d];
          _PopLink(u, &deg_table_[d]);
          node = _Meld(node, u);
          assert(node->deg == d+1);
        }
        _PushLink(node, &deg_table_[node->deg]);
      } else { // Single tree at current degree
        if (!root_ or _CompareNodePriority(root_, deg_table_[k]))
          root_ = deg_table_[k];
        ++k;
      }
    }
  }

  void _Consolidate(node_ptr node) {
    assert(node->parent);
    auto p = node->parent;
    if (p->marked) {
      assert(p->parent); // Parent is not one of the roots.
      _Consolidate(p);
    }
    assert(!p->marked);
    if (p->parent) {
      p->marked = true;
    } else {
      _PopLink(p, &deg_table_[p->deg]);
      _PushLink(p, &deg_table_[p->deg-1]);
    }
    _PopLink(node, &p->child);
    p->deg--;
    node->parent = nullptr;
    node->marked = false;
    _PushLink(node, &deg_table_[node->deg]);
  }

};
#line 5 "include/mtl/min_cost_flow.hpp"

template<typename C>
struct MinCostFlowPath {
  int t, rev, cap;
  C cost;
  MinCostFlowPath(int t, int rev, int cap, C cost)
      : t(t), rev(rev), cap(cap), cost(cost) {}
};

template<typename C>
struct MinCostFlowGraph {
  const C INF = std::numeric_limits<C>::max();
  int n;
  std::vector<std::vector<MinCostFlowPath<C>>> g;
  std::vector<C> dist, h;
  std::vector<int> prevv, preve;
  explicit MinCostFlowGraph(int n)
      : n(n), g(n), dist(n), h(n), prevv(n), preve(n) {}

  void add_edge(int a, int b, int cap, C cost) {
    g[a].emplace_back(b, g[b].size(), cap, cost);
    g[b].emplace_back(a, g[a].size()-1, 0, -cost);
  }

  std::pair<int, C> flow(int s, int t, int flow_limit = std::numeric_limits<int>::max()) {
    h.assign(n, 0);
    auto f = 0;
    C res = 0;
    FibonacciHeap<C, std::greater<C>> qs(n);
    while (f < flow_limit) {
      dist.assign(n, INF);
      dist[s] = 0;
      qs.push(s, 0);
      while (!qs.empty()) {
        auto q = qs.top(); qs.pop();
        auto u = q.first;
        auto d = q.second;
        for (size_t i = 0; i < g[u].size(); i++) {
          auto& e = g[u][i];
          if (e.cap == 0) continue;
          auto cost = d + e.cost + h[u] - h[e.t];
          if (cost >= dist[e.t]) continue;
          dist[e.t] = cost;
          qs.push(e.t, cost);
          prevv[e.t] = u;
          preve[e.t] = i;
        }
      }
      if (dist[t] == INF)
        break;
      for (int i = 0; i < n; i++) if (dist[i] != INF)
        h[i] += dist[i];
      int d = flow_limit - f;
      C cost_sum = 0;
      for (int i = t; i != s; i = prevv[i]) {
        auto& e = g[prevv[i]][preve[i]];
        d = std::min(d, e.cap);
        cost_sum += e.cost;
      }
      f += d;
      res += (C) d * cost_sum;
      for (int i = t; i != s; i = prevv[i]) {
        auto& e = g[prevv[i]][preve[i]];
        e.cap -= d;
        g[i][e.rev].cap += d;
      }
    }
    return std::make_pair(f, res);
  }
};
#line 3 "test/aoj/min_cost_flow.test.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int V,E,F; cin>>V>>E>>F;
  MinCostFlowGraph<int> mcfg(V);
  for (int i = 0; i < E; i++) {
    int u,v,c,d; cin>>u>>v>>c>>d;
    mcfg.add_edge(u, v, c, d);
  }
  auto res = mcfg.flow(0, V-1, F);
  cout << (res.first == F ? res.second : -1) << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	3 MB
g++	01_small_00.in	AC	5 ms	3 MB
g++	01_small_01.in	AC	5 ms	3 MB
g++	01_small_02.in	AC	5 ms	3 MB
g++	01_small_03.in	AC	5 ms	3 MB
g++	02_corner_00.in	AC	5 ms	3 MB
g++	02_corner_01.in	AC	5 ms	3 MB
g++	02_corner_02.in	AC	5 ms	3 MB
g++	03_random_00.in	AC	5 ms	3 MB
g++	03_random_01.in	AC	5 ms	3 MB
g++	03_random_02.in	AC	5 ms	3 MB
g++	03_random_03.in	AC	5 ms	3 MB
g++	03_random_04.in	AC	5 ms	3 MB
g++	03_random_05.in	AC	5 ms	3 MB
g++	03_random_06.in	AC	6 ms	3 MB
g++	03_random_07.in	AC	5 ms	3 MB
g++	04_rand_00.in	AC	5 ms	3 MB
g++	04_rand_01.in	AC	5 ms	3 MB
g++	04_rand_02.in	AC	5 ms	3 MB
g++	04_rand_03.in	AC	5 ms	3 MB
g++	04_rand_04.in	AC	5 ms	3 MB
g++	04_rand_05.in	AC	5 ms	3 MB
g++	04_rand_06.in	AC	5 ms	3 MB
g++	04_rand_07.in	AC	5 ms	3 MB
g++	05_large_00.in	AC	6 ms	4 MB
g++	05_large_01.in	AC	6 ms	4 MB
g++	05_large_02.in	AC	6 ms	4 MB
g++	05_large_03.in	AC	6 ms	4 MB
g++	06_biased_00.in	AC	5 ms	3 MB
g++	06_biased_01.in	AC	6 ms	4 MB
g++	06_biased_02.in	AC	5 ms	3 MB
g++	06_biased_03.in	AC	6 ms	4 MB
clang++	00_sample_00.in	AC	5 ms	3 MB
clang++	01_small_00.in	AC	5 ms	3 MB
clang++	01_small_01.in	AC	5 ms	3 MB
clang++	01_small_02.in	AC	5 ms	3 MB
clang++	01_small_03.in	AC	5 ms	3 MB
clang++	02_corner_00.in	AC	5 ms	3 MB
clang++	02_corner_01.in	AC	5 ms	3 MB
clang++	02_corner_02.in	AC	5 ms	3 MB
clang++	03_random_00.in	AC	5 ms	3 MB
clang++	03_random_01.in	AC	5 ms	3 MB
clang++	03_random_02.in	AC	5 ms	3 MB
clang++	03_random_03.in	AC	5 ms	3 MB
clang++	03_random_04.in	AC	5 ms	3 MB
clang++	03_random_05.in	AC	6 ms	3 MB
clang++	03_random_06.in	AC	5 ms	3 MB
clang++	03_random_07.in	AC	6 ms	4 MB
clang++	04_rand_00.in	AC	5 ms	3 MB
clang++	04_rand_01.in	AC	5 ms	3 MB
clang++	04_rand_02.in	AC	5 ms	3 MB
clang++	04_rand_03.in	AC	5 ms	3 MB
clang++	04_rand_04.in	AC	5 ms	3 MB
clang++	04_rand_05.in	AC	5 ms	3 MB
clang++	04_rand_06.in	AC	5 ms	3 MB
clang++	04_rand_07.in	AC	5 ms	3 MB
clang++	05_large_00.in	AC	6 ms	3 MB
clang++	05_large_01.in	AC	6 ms	4 MB
clang++	05_large_02.in	AC	6 ms	4 MB
clang++	05_large_03.in	AC	6 ms	3 MB
clang++	06_biased_00.in	AC	5 ms	3 MB
clang++	06_biased_01.in	AC	6 ms	4 MB
clang++	06_biased_02.in	AC	6 ms	3 MB
clang++	06_biased_03.in	AC	6 ms	4 MB

Back to top page