test/MinCostFlow.test.cpp

• View this file on GitHub
• Last update: 2021-09-12 23:44:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_6_B

Depends on

• Min Cost Flow (Primal Dual) (graph/MinCostFlow.cpp)
• template/template.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_6_B"

#include "../graph/MinCostFlow.cpp"
int main(){
    ll V,E,F;
    cin>>V>>E>>F;
    PrimalDual FL(V);
    rep(i,E){
        int u,v,c,d;cin>>u>>v>>c>>d;
        FL.add_edge(u,v,c,d);
    }
    cout<<FL.minCostFlow(0,V-1,F)<<"\n";
}

#line 1 "test/MinCostFlow.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_6_B"

#line 2 "template/template.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = 1; i < n; i++)
#define rev(i, n) for (int i = n - 1; i >= 0; i--)
#define REV(i, n) for (int i = n - 1; i > 0; i--)
#define all(v) v.begin(), v.end()
#define PL pair<ll, ll>
#define PI pair<int, int>
#define pi acos(-1)
#define len(s) (int)s.size()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), v.end());
#define comid(v, x) lower_bound(all(v), x) - v.begin()

template<class T>
using prique=priority_queue<T,vector<T>,greater<>>;

template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
constexpr ll inf = 3e18;
#line 3 "graph/MinCostFlow.cpp"

struct PrimalDual {
    struct edge {
        ll to, cap, cost, rev;
    };
    vector<vector<edge>> graph;
    bool negative = false;
    void add_edge(ll from, ll to, ll cap, ll cost) {
        graph[from].push_back({to, cap, cost, len(graph[to])});
        graph[to].push_back({from, 0ll, -cost, len(graph[from]) - 1});
        if (cost < 0) negative = true;
    }
    ll minCostFlow(ll s, ll t, ll f) {
        ll V = len(graph);
        vector<ll> potential(V), minCost, prevv(V, -1), preve(V, -1);
        ll res = 0;
        if (negative) {
            minCost.assign(V, inf);
            minCost[s] = 0;
            rep(_, V - 1) {
                rep(i, V) {
                    rep(j, len(graph[i])) {
                        edge &e = graph[i][j];
                        if (e.cap > 0 && chmin(minCost[e.to], minCost[i] + e.cost + potential[i] - potential[e.to])) {
                            prevv[e.to] = i;
                            preve[e.to] = j;
                        }
                    }
                }
            }
            if (minCost[t] == inf) return -1;
            rep(i, V) potential[i] += minCost[i];
            for (ll i = t; i != s; i = prevv[i]) {
                graph[prevv[i]][preve[i]].cap--;
                graph[i][graph[prevv[i]][preve[i]].rev].cap++;
            }
            res += potential[t];
            f--;
        }

        while (f > 0) {
            minCost.assign(V, inf);
            minCost[s] = 0;
            priority_queue<PL, vector<PL>, greater<>> que;
            que.push({0, s});
            while (!que.empty()) {
                PL p = que.top();
                que.pop();
                if (minCost[p.second] < p.first) continue;
                rep(i, len(graph[p.second])) {
                    edge &e = graph[p.second][i];
                    if (e.cap > 0 && chmin(minCost[e.to], p.first + e.cost + potential[p.second] - potential[e.to])) {
                        prevv[e.to] = p.second;
                        preve[e.to] = i;
                        que.push({minCost[e.to], e.to});
                    }
                }
            }

            if (minCost[t] == inf) return -1;
            rep(i, V) potential[i] += minCost[i];
            ll addflow = f;
            for (ll i = t; i != s; i = prevv[i]) chmin(addflow, graph[prevv[i]][preve[i]].cap);
            f -= addflow;
            res += addflow * potential[t];
            for (ll i = t; i != s; i = prevv[i]) {
                edge &e = graph[prevv[i]][preve[i]];
                e.cap -= addflow;
                graph[i][e.rev].cap += addflow;
            }
        }
        return res;
    }
    PrimalDual(ll V) : graph(V){};
};
/*
@brief Min Cost Flow (Primal Dual)
@docs docs/MinCostFlow.md
*/
#line 4 "test/MinCostFlow.test.cpp"
int main(){
    ll V,E,F;
    cin>>V>>E>>F;
    PrimalDual FL(V);
    rep(i,E){
        int u,v,c,d;cin>>u>>v>>c>>d;
        FL.add_edge(u,v,c,d);
    }
    cout<<FL.minCostFlow(0,V-1,F)<<"\n";
}

Back to top page