Library
This documentation is automatically generated by online-judge-tools/verification-helper
Graph/Aizu/aizu_grl_6_b_minimum_cost_flow.test.cpp
- View this file on GitHub
- Last update: 2026-10-17 00:46:18+07:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_B
Depends on
template.h
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_B"
#include "../../template.h"
#include "../Flow/MinCostFlow.h"
void solve() {
int n, m; ll F; cin >> n >> m >> F;
MinCostFlow mcf(n);
for (int i = 0; i < m; i++) {
int u, v; ll c, d; cin >> u >> v >> c >> d;
mcf.addEdge(u, v, c, d);
}
auto [flow, cost] = mcf.minCostFlow(0, n-1, F);
cout << (flow < F ? -1 : cost) << '\n';
}#line 1 "Graph/Aizu/aizu_grl_6_b_minimum_cost_flow.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_B"
#line 2 "template.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll r) { return uniform_int_distribution<ll>(0, r - 1)(rng); }
const int mod = 998244353;
void solve();
int main() {
// if (FILE* f = fopen(TASK ".inp", "r")) {
// fclose(f);
// freopen(TASK ".inp", "r", stdin);
// freopen(TASK ".out", "w", stdout);
// }
ios_base::sync_with_stdio(false);cin.tie(NULL);
// cin.exceptions(cin.failbit);
// int t; cin >> t;
// while(t--)
solve();
cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
return 0;
}
#line 1 "Graph/Flow/MinCostFlow.h"
// // spfa version
// struct MinCostFlow {
// struct Edge {
// int v, rev;
// ll cap, flow, cost;
// };
// const ll INF = LLONG_MAX / 4;
// int n;
// vector<vector<Edge>> g;
// vector<ll> d;
// vector<int> trace, id;
// vector<bool> inq;
// MinCostFlow(int n) : n(n), g(n + 1) {}
// void addEdge(int u, int v, ll cap, ll cost) {
// int iu = g[u].size(), iv = g[v].size() + (u == v);
// g[u].push_back({v, iv, cap, 0, cost});
// g[v].push_back({u, iu, 0, 0, -cost});
// }
// bool spfa(int s, int t) {
// d.assign(n + 1, INF);
// trace.assign(n + 1, -1), id.assign(n + 1, -1), inq.assign(n + 1, false);
// queue<int> q;
// d[s] = 0, q.push(s), inq[s] = true;
// while (!q.empty()) {
// int u = q.front(); q.pop();
// inq[u] = false;
// for (int i = 0; i < (int)g[u].size(); i++) {
// Edge &e = g[u][i];
// if (e.cap - e.flow == 0 || d[u] + e.cost >= d[e.v]) continue;
// d[e.v] = d[u] + e.cost;
// trace[e.v] = u, id[e.v] = i;
// if (!inq[e.v]) inq[e.v] = true, q.push(e.v);
// }
// }
// return d[t] < INF;
// }
// pair<ll, ll> minCostFlow(int s, int t, ll k = LLONG_MAX) {
// ll flow = 0, cost = 0;
// while (flow < k && spfa(s, t)) {
// ll delta = k - flow;
// for (int v = t; v != s; v = trace[v]) {
// Edge &e = g[trace[v]][id[v]];
// delta = min(delta, e.cap - e.flow);
// }
// for (int v = t; v != s; v = trace[v]) {
// Edge &e = g[trace[v]][id[v]];
// e.flow += delta;
// g[v][e.rev].flow -= delta;
// }
// flow += delta;
// cost += delta * d[t];
// }
// return {flow, cost};
// }
// };
// vnoi version (dijkstra + potential)
struct MinCostFlow {
struct Edge {
int v, rev;
ll cap, flow, cost;
};
const ll INF = LLONG_MAX / 4;
int n;
bool negCost = false;
vector<vector<Edge>> g;
vector<ll> pi, d;
vector<int> trace, id;
MinCostFlow(int n) : n(n), g(n + 1) {}
void addEdge(int u, int v, ll cap, ll cost) {
int iu = g[u].size(), iv = g[v].size() + (u == v);
g[u].push_back({v, iv, cap, 0, cost});
g[v].push_back({u, iu, 0, 0, -cost});
negCost |= cost < 0;
}
void bellmanFord(int s) {
pi.assign(n + 1, INF);
pi[s] = 0;
for (int it = 0; it < n; it++) {
bool upd = false;
for (int u = 0; u <= n; u++) {
if (pi[u] == INF) continue;
for (Edge &e : g[u])
if (e.cap - e.flow > 0 && pi[u] + e.cost < pi[e.v]) pi[e.v] = pi[u] + e.cost, upd = true;
}
if (!upd) break;
}
}
bool dijkstra(int s, int t) {
d.assign(n + 1, INF);
trace.assign(n + 1, -1), id.assign(n + 1, -1);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
d[s] = 0, pq.push({0, s});
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != d[u]) continue;
for (int i = 0; i < (int)g[u].size(); i++) {
Edge &e = g[u][i];
if (e.cap - e.flow == 0) continue;
ll w = e.cost + pi[u] - pi[e.v];
if (d[u] + w >= d[e.v]) continue;
d[e.v] = d[u] + w;
trace[e.v] = u, id[e.v] = i;
pq.push({d[e.v], e.v});
}
}
for (int u = 0; u <= n; u++)
if (d[u] < INF) pi[u] += d[u];
return d[t] < INF;
}
pair<ll, ll> minCostFlow(int s, int t, ll k = LLONG_MAX) {
pi.assign(n + 1, 0);
if (negCost) bellmanFord(s);
ll flow = 0, cost = 0;
while (flow < k && dijkstra(s, t)) {
ll delta = k - flow, pathCost = 0;
for (int v = t; v != s; v = trace[v]) {
Edge &e = g[trace[v]][id[v]];
delta = min(delta, e.cap - e.flow);
pathCost += e.cost;
}
for (int v = t; v != s; v = trace[v]) {
Edge &e = g[trace[v]][id[v]];
e.flow += delta;
g[v][e.rev].flow -= delta;
}
flow += delta;
cost += delta * pathCost;
}
return {flow, cost};
}
};
#line 5 "Graph/Aizu/aizu_grl_6_b_minimum_cost_flow.test.cpp"
void solve() {
int n, m; ll F; cin >> n >> m >> F;
MinCostFlow mcf(n);
for (int i = 0; i < m; i++) {
int u, v; ll c, d; cin >> u >> v >> c >> d;
mcf.addEdge(u, v, c, d);
}
auto [flow, cost] = mcf.minCostFlow(0, n-1, F);
cout << (flow < F ? -1 : cost) << '\n';
}