#include <bits/stdc++.h> using namespace std; #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B&lang=ja" #include "../graph/primal_dual2.cpp" #include "../template/const.hpp" int main() { int n, m, f; cin >> n >> m >> f; PrimalDual2<int, int, INF> pd(n); int u, v, c, d; for (int i = 0; i < m; i++) { cin >> u >> v >> c >> d; pd.add_edge(u, v, c, d); } auto [actual_f, cost] = pd.solve(0, n - 1, f); if (actual_f < f) cout << -1 << '\n'; else cout << cost << '\n'; return 0; }
#line 1 "test/primal_dual2.test.cpp" #include <bits/stdc++.h> using namespace std; #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B&lang=ja" #line 3 "graph/primal_dual2.cpp" using namespace std; // PrimalDual2 // berumanford法を用いて最小費用流を求める. // 最初のグラフには負閉路が含まれてはいけない. template <typename Cap, typename Cost, const Cost INF> struct PrimalDual2 { struct edge { int to; Cap cap; Cost cost; int rev; }; int n; vector<vector<edge>> G; vector<Cost> dist; vector<int> prevv, preve; PrimalDual2(int n) : n(n) { G.resize(n); dist.resize(n); prevv.resize(n); preve.resize(n); } // add_edge // fromからtoへ容量cap, コストcostの辺を張る. // 制約: 0 <= from,to < n,cap >= 0, void add_edge(int from, int to, Cap cap, Cost cost) { G[from].push_back((edge){to, cap, cost, (int)G[to].size()}); G[to].push_back((edge){from, 0, -cost, (int)G[from].size() - 1}); } // beruman int beruman(int s, int t) { fill(dist.begin(), dist.end(), INF); dist[s] = 0; bool update = true; while (update) { update = false; for (int v = 0; v < n; v++) { if (dist[v] == INF) continue; for (int i = 0; i < (int)G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; prevv[e.to] = v; preve[e.to] = i; update = true; } } } } return dist[t] < INF; } // solve // sからtへfだけ流すための最小費用を求める. // 制約: 0 <= s,t < n,f >= 0 // 計算量: O(f|V||E|) pair<Cap, Cost> solve(int s, int t, Cap f) { Cost ret_cost = 0; Cap ret_flow = 0; while (ret_flow < f) { if (!beruman(s, t)) break; Cap d = f - ret_flow; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } ret_flow += d; ret_cost += d * dist[t]; for (int v = t; v != s; v = prevv[v]) { edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return {ret_flow, ret_cost}; } }; #line 2 "template/const.hpp" constexpr int INF = 1000'000'000; constexpr long long HINF = 4000'000'000'000'000'000; constexpr long long MOD = 998244353; constexpr double EPS = 1e-6; constexpr double PI = 3.14159265358979; #line 7 "test/primal_dual2.test.cpp" int main() { int n, m, f; cin >> n >> m >> f; PrimalDual2<int, int, INF> pd(n); int u, v, c, d; for (int i = 0; i < m; i++) { cin >> u >> v >> c >> d; pd.add_edge(u, v, c, d); } auto [actual_f, cost] = pd.solve(0, n - 1, f); if (actual_f < f) cout << -1 << '\n'; else cout << cost << '\n'; return 0; }