test/graph/primaldual.test.cpp

• View this file on GitHub
• Last update: 2025-11-13 05:48:47+08:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B

Depends on

• src/graph/primaldual.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;

#include "../../src/graph/primaldual.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m, maxf;
  cin >> n >> m >> maxf;
  PrimalDual<ll> pd(n);
  for (int _ = 0; _ < m; _++) {
    int u, v, c, w;
    cin >> u >> v >> c >> w;
    pd.adde(u, v, c, w);
  }
  auto [maxflow, mincost] = pd.flow(0, n - 1, maxf);
  cout << (maxflow == maxf ? mincost : -1) << "\n";
  return 0;
}

#line 1 "test/graph/primaldual.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;

#line 1 "src/graph/primaldual.hpp"
// 时间复杂度: $\mathcal{O}(mf \log n)$.
template <typename T>
struct PrimalDual {
  struct Edge {
    int u, v;
    T cap, cost, flow;
  };
  static constexpr T INF = numeric_limits<T>::max();
  int n, _s, _t;
  vector<int> prev;
  vector<T> h, dist;
  vector<vector<int>> G;
  vector<Edge> E;
  PrimalDual(int n) : n(n), prev(n), h(n), dist(n), G(n) {}
  void adde(int u, int v, T cap, T cost) {
    G[u].PUSHB(E.size()), E.PUSHB({u, v, cap, cost, 0});
    G[v].PUSHB(E.size()), E.PUSHB({v, u, 0, -cost, 0});
  }
  pair<T, T> flow(int s, int t, T maxf = INF) {
    _s = s, _t = t;
    bellman_ford();
    T maxflow = 0, mincost = 0;
    while (maxflow < maxf && dijkstra()) {
      T aug = maxf - maxflow;
      for (int i = 0; i < n; i++)
        if (dist[i] != INF) h[i] += dist[i];
      for (int p = _t; p != _s; p = E[prev[p] ^ 1].v)
        aug = min(aug, E[prev[p]].cap - E[prev[p]].flow);
      for (int p = _t; p != _s; p = E[prev[p] ^ 1].v)
        E[prev[p]].flow += aug, E[prev[p] ^ 1].flow -= aug;
      maxflow += aug, mincost += aug * h[_t];
    }
    return {maxflow, mincost};
  }

 private:
  void bellman_ford() {
    queue<int> que;
    vector<char> inque(n);
    fill(ALL(h), INF);
    h[_s] = 0;
    inque[_s] = 1;
    que.push(_s);
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      inque[u] = 0;
      for (int i : G[u]) {
        const auto& [_, v, cap, cost, flow] = E[i];
        if (cap <= flow || h[v] <= h[u] + cost) continue;
        h[v] = h[u] + cost;
        if (!inque[v]) {
          inque[v] = 1;
          que.push(v);
        }
      }
    }
  }
  bool dijkstra() {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;
    fill(ALL(dist), INF);
    dist[_s] = 0;
    pq.push({0, _s});
    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      if (dist[u] != d) continue;
      for (int i : G[u]) {
        auto& [_, v, cap, cost, flow] = E[i];
        if (cap <= flow || dist[v] <= d + cost + h[u] - h[v]) continue;
        dist[v] = d + cost + h[u] - h[v];
        prev[v] = i;
        pq.push({dist[v], v});
      }
    }
    return dist[_t] != INF;
  }
};
#line 9 "test/graph/primaldual.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m, maxf;
  cin >> n >> m >> maxf;
  PrimalDual<ll> pd(n);
  for (int _ = 0; _ < m; _++) {
    int u, v, c, w;
    cin >> u >> v >> c >> w;
    pd.adde(u, v, c, w);
  }
  auto [maxflow, mincost] = pd.flow(0, n - 1, maxf);
  cout << (maxflow == maxf ? mincost : -1) << "\n";
  return 0;
}

Test cases

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

Back to top page