mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

最小費用流（primal-dual法）
(graph/primal_dual.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "graph/primal_dual.hpp"

最小費用流

最小費用流を求める。負の辺を張ることはできない。

使い方

• primal_dual<T>(int V) : コンストラクタ。頂点数 $V$ の最小費用流の構築の準備を行う。
• add_edge(int from, int to, T cap, T cost) : $from$ から $to$ へ、容量 $cap$ で $1$ 流量当たりのコストが $cost$ の辺を張る $O(1)$
• pair<bool, T> min_cost_flow(int s, int t, T f) : $s$ から $t$ へ、流量 $f$ を流せるだけ流したときの最小費用流を求める。true が返ったときは、$f$ 流すことができたことを示す。 最悪計算量 $O(fV^2)$

Verified with

• verify/aoj/grl/6_B.test.cpp

Code

#pragma once

#include<functional>
#include<limits>
#include<utility>
#include<queue>
#include<vector>

template<typename T>
struct primal_dual{
	struct edge {
		int to;
		T cap, cost, rev;
		T max_cap;
	};
	int V;
	T infty;
	std::vector<std::vector<edge>> G;
	std::vector<T> h, dist;
	std::vector<int> prevv, preve;
	std::vector<bool> used_edge;

	primal_dual(int _V) : V(_V), infty(std::numeric_limits<T>::max()/2) {
		G.resize(V);
		h.resize(V);
		dist.resize(V);
		prevv.resize(V);
		preve.resize(V);
		used_edge.resize(V);
	}

	void add_edge(int from, int to, T cap, T cost){
		G[from].push_back((edge){to, cap, cost, (int)G[to].size(), cap});
		G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1, 0});
		used_edge[from] = true;
		used_edge[to] = true;
	}

	std::pair<bool, T> min_cost_flow(int s, int t, T f){
		T res = 0;
		while(f > 0){
			std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> que;
			dist.assign(V, infty);
			dist[s] = 0;
			que.push({0, s});
			while(not que.empty()){
				auto [cst, v] = que.top();
				que.pop();
				if(dist[v] < cst)continue;
				for(int i = 0;i < (int)G[v].size();i++){
					auto &e = G[v][i];
					if(e.cap > 0 && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to]){
						dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push({dist[e.to], e.to});
					}
				}
			}
			if(dist[t] == infty){
				return make_pair(false, res);
			}
			for(int v = 0;v < V;v++){
				if(not used_edge[v])continue;
				h[v] += dist[v];
			}
			T d = f;
			for(int v = t;v != s;v = prevv[v]){
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d*h[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 make_pair(true, res);
	}
};

#line 2 "graph/primal_dual.hpp"

#include<functional>
#include<limits>
#include<utility>
#include<queue>
#include<vector>

template<typename T>
struct primal_dual{
	struct edge {
		int to;
		T cap, cost, rev;
		T max_cap;
	};
	int V;
	T infty;
	std::vector<std::vector<edge>> G;
	std::vector<T> h, dist;
	std::vector<int> prevv, preve;
	std::vector<bool> used_edge;

	primal_dual(int _V) : V(_V), infty(std::numeric_limits<T>::max()/2) {
		G.resize(V);
		h.resize(V);
		dist.resize(V);
		prevv.resize(V);
		preve.resize(V);
		used_edge.resize(V);
	}

	void add_edge(int from, int to, T cap, T cost){
		G[from].push_back((edge){to, cap, cost, (int)G[to].size(), cap});
		G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1, 0});
		used_edge[from] = true;
		used_edge[to] = true;
	}

	std::pair<bool, T> min_cost_flow(int s, int t, T f){
		T res = 0;
		while(f > 0){
			std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> que;
			dist.assign(V, infty);
			dist[s] = 0;
			que.push({0, s});
			while(not que.empty()){
				auto [cst, v] = que.top();
				que.pop();
				if(dist[v] < cst)continue;
				for(int i = 0;i < (int)G[v].size();i++){
					auto &e = G[v][i];
					if(e.cap > 0 && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to]){
						dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push({dist[e.to], e.to});
					}
				}
			}
			if(dist[t] == infty){
				return make_pair(false, res);
			}
			for(int v = 0;v < V;v++){
				if(not used_edge[v])continue;
				h[v] += dist[v];
			}
			T d = f;
			for(int v = t;v != s;v = prevv[v]){
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d*h[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 make_pair(true, res);
	}
};

Back to top page