min cost flow
(graph/mcf_graph.hpp)

• View this file on GitHub
• Last update: 2023-06-02 02:20:37+09:00
• Include: #include "graph/mcf_graph.hpp"

説明

最小費用流を最短路反復法で求める。YNU ICPC Library を改変してより高速に書けるようにした。

Cap, Cost はともに long long 型である。

コンストラクタ

MinCostFlow graph(int n)

n 頂点 0 辺のグラフを作る。

add_edge(int from, int to, ll cap, ll cost)

from→to へ最大容量 cap、流量 0、コスト cost の辺を追加する。

flow(int s, int t, ll u)

頂点 s から t へ流量 u 流したときの最小コストを求める。流れない場合は -1 が返される。

計算量は、流量を $F$, 頂点数を $V$, 辺の数を $E$ として $O(F(V+E)\log(V+E))$ である。

実装例

int main(){
	int v,e,f;
	cin >> v >> e >> f;
	lib::MinCostFlow mcf(v);
	for (int i=0;i<e;i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		mcf.add_edge(a,b,c,d);
	}
	ll ans = mcf.flow(0,v-1,f);
	cout << ans << endl;
}

Depends on

• テンプレート (template/template.hpp)

Verified with

• test/graph/Minimum_Flow.test.cpp

Code

#pragma once
#include "../template/template.hpp"

namespace lib {
using namespace std;

struct MinCostFlow {
    int n;
    vector<vector<vector<ll>>> g;
    vector<ll> h, dis;
    vector<int> pv, pe;

    MinCostFlow(int v) : n(v), g(v), dis(v), pv(v), pe(v) {}

    void add_edge(int from, int to, ll cap, ll cost) {
        g[from].push_back({to, cap, cost, (int)g[to].size()});
        g[to].push_back({from, 0, -cost, (int)g[from].size()-1});
    }

    ll flow(int s, int t, ll f) {
        ll res = 0;
        h.assign(n, 0);
        using Q = pair<ll, int>;
        while (f > 0) {
            priority_queue<Q, vector<Q>, greater<Q>> que;
            dis.assign(n, LLONG_MAX);
            dis[s] = 0;
            que.push({0, s});
            while (que.size()) {
                Q q = que.top();
                int v = q.second;
                que.pop();
                if (dis[v] < q.first) continue;
				rep(i,0,g[v].size()){
                    auto edge = g[v][i];
                    int to = edge[0];
                    ll cap = edge[1], cost = edge[2];
                    if (cap > 0 and dis[to] > dis[v] + cost + h[v] - h[to]) {
                        dis[to] = dis[v] + cost + h[v] - h[to];
                        pv[to] = v;
                        pe[to] = i;
                        que.push({dis[to], to});
                    }
                }
            }
            if (dis[t] == LLONG_MAX) return -1;
            rep(i,0,n) h[i] += dis[i];
            ll d = f;
            for (int i=t; i!=s; i=pv[i]) d = min(d, g[pv[i]][pe[i]][1]);
            f -= d;
            res += d * h[t];
            for (int i=t; i!=s; i=pv[i]) {
                auto& edge = g[pv[i]][pe[i]];
                edge[1] -= d;
                g[i][edge[3]][1] += d;
            }
        }
        return res;
    }
};

}

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 3 "graph/mcf_graph.hpp"

namespace lib {
using namespace std;

struct MinCostFlow {
    int n;
    vector<vector<vector<ll>>> g;
    vector<ll> h, dis;
    vector<int> pv, pe;

    MinCostFlow(int v) : n(v), g(v), dis(v), pv(v), pe(v) {}

    void add_edge(int from, int to, ll cap, ll cost) {
        g[from].push_back({to, cap, cost, (int)g[to].size()});
        g[to].push_back({from, 0, -cost, (int)g[from].size()-1});
    }

    ll flow(int s, int t, ll f) {
        ll res = 0;
        h.assign(n, 0);
        using Q = pair<ll, int>;
        while (f > 0) {
            priority_queue<Q, vector<Q>, greater<Q>> que;
            dis.assign(n, LLONG_MAX);
            dis[s] = 0;
            que.push({0, s});
            while (que.size()) {
                Q q = que.top();
                int v = q.second;
                que.pop();
                if (dis[v] < q.first) continue;
				rep(i,0,g[v].size()){
                    auto edge = g[v][i];
                    int to = edge[0];
                    ll cap = edge[1], cost = edge[2];
                    if (cap > 0 and dis[to] > dis[v] + cost + h[v] - h[to]) {
                        dis[to] = dis[v] + cost + h[v] - h[to];
                        pv[to] = v;
                        pe[to] = i;
                        que.push({dis[to], to});
                    }
                }
            }
            if (dis[t] == LLONG_MAX) return -1;
            rep(i,0,n) h[i] += dis[i];
            ll d = f;
            for (int i=t; i!=s; i=pv[i]) d = min(d, g[pv[i]][pe[i]][1]);
            f -= d;
            res += d * h[t];
            for (int i=t; i!=s; i=pv[i]) {
                auto& edge = g[pv[i]][pe[i]];
                edge[1] -= d;
                g[i][edge[3]][1] += d;
            }
        }
        return res;
    }
};

}

Back to top page