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

割当問題（ハンガリアン法）
(graph/hungarian.hpp)

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

ハンガリアン法

使い方

行が人、列が仕事を表す $N$ 行 $N$ 列の行列を用意する。（割り当てがない場合は、$A_{i, j} = 0$ としてよい）

• vector<int> hungarian<bool is_min, typename T>(vector<vector<T>> A) : 割当問題における
  • is_min が true の時 : 最小重み最大マッチングの割り当てを返す $O(N^3)$
  • is_min が false の時 : 最大重み最大マッチングの割り当てを返す $O(N^3)$

メモ

割当問題をハンガリアン法で解く。

• 最小重み最大マッチングを、最小費用流で解けることを理解するのが前提
• $i$ からスタートする増加路を考える
• 二部グラフの最大マッチングの形のグラフになっていることを活用して、（ダイクストラ法などのグラフアルゴリズムを使うことなく）ポテンシャルの計算をするのが肝っぽい

Verified with

• verify/aoj/id/2828.test.cpp
• verify/yosupo/assignment.test.cpp
• verify/yosupo/assignment_negative.test.cpp

Code

#pragma once

#include<limits>
#include<numeric>
#include<vector>

template<bool is_min, typename T>
std::vector<int> hungarian(std::vector<std::vector<T>> a) {
	T infty = std::numeric_limits<T>::max()/T(2);
	int n = (int)a.size();
	
	if(not is_min){
		for(int i = 0;i < n;i++){
			for(int j = 0; j < n;j++){
				a[i][j] = -a[i][j];
			}
		}
	}

	std::vector<int> p(n);
	std::iota(p.begin(), p.end(), 0);

	std::vector<T> h = {0};
	h.reserve(n);
	for(int i = 1;i < n;i++){
		h.push_back(0);
		std::vector<T> d(i+1, infty);
		std::vector<int> pre(i+1, -1);
		std::vector<bool> used(i+1, false);

		d[i] = 0;
		pre[i] = i;

		for(int _ = 0;_ <= i;_++){
			T min_d = infty;
			int v = -1;
			for(int j = 0;j <= i;j++){
				if(not used[j] && min_d > d[j]-h[j]){
					min_d = d[j]-h[j];
					v = j;
				}
			}
				
			used[v] = true;

			for(int j = 0;j <= i;j++){
				if(not used[j] || j == i){
					T nd = d[v] - a[v][p[v]] + a[j][p[v]];
					if(d[j] > nd){
						d[j] = nd;
						pre[j] = v;
					}
				}
			}
		}

		int cur = i;
		while(pre[cur] != i){
			std::swap(p[cur], p[pre[cur]]);
			cur = pre[cur];
		}
		h = d;
	}
	return p;
}

#line 2 "graph/hungarian.hpp"

#include<limits>
#include<numeric>
#include<vector>

template<bool is_min, typename T>
std::vector<int> hungarian(std::vector<std::vector<T>> a) {
	T infty = std::numeric_limits<T>::max()/T(2);
	int n = (int)a.size();
	
	if(not is_min){
		for(int i = 0;i < n;i++){
			for(int j = 0; j < n;j++){
				a[i][j] = -a[i][j];
			}
		}
	}

	std::vector<int> p(n);
	std::iota(p.begin(), p.end(), 0);

	std::vector<T> h = {0};
	h.reserve(n);
	for(int i = 1;i < n;i++){
		h.push_back(0);
		std::vector<T> d(i+1, infty);
		std::vector<int> pre(i+1, -1);
		std::vector<bool> used(i+1, false);

		d[i] = 0;
		pre[i] = i;

		for(int _ = 0;_ <= i;_++){
			T min_d = infty;
			int v = -1;
			for(int j = 0;j <= i;j++){
				if(not used[j] && min_d > d[j]-h[j]){
					min_d = d[j]-h[j];
					v = j;
				}
			}
				
			used[v] = true;

			for(int j = 0;j <= i;j++){
				if(not used[j] || j == i){
					T nd = d[v] - a[v][p[v]] + a[j][p[v]];
					if(d[j] > nd){
						d[j] = nd;
						pre[j] = v;
					}
				}
			}
		}

		int cur = i;
		while(pre[cur] != i){
			std::swap(p[cur], p[pre[cur]]);
			cur = pre[cur];
		}
		h = d;
	}
	return p;
}

Back to top page