最小シュタイナー木
(Graph/steiner_tree.hpp)

• View this file on GitHub
• Last update: 2024-08-03 19:16:34+09:00
• Include: #include "Graph/steiner_tree.hpp"

概要

グラフにおいて、いくつかの頂点集合からなる $\text{terminal}$ を連結にするのに必要な最小コストを求める。

頂点数 $N$, 辺数 $M$, $\text{terminal}$ の個数を $K$ として計算量 $\text{O} (3^{K}N + 2^{K}(N + M) \log M)$

Verified with

• Test/yukicoder/yuki0114.test.cpp

Code

template <class T> std::vector<T> steiner_tree(std::vector<std::vector<std::pair<int, T>>> &G, 
								std::vector<int> &terminal){
    const int N = G.size(), t = terminal.size();
	if(t == 0) {
		std::vector<T> ans(N);
		return ans;
	}
	std::vector<std::vector<T>> dp(1 << t, std::vector<T>(N, std::numeric_limits<T>::max() / 2));
	for(int i = 0; i < t; i++){
		assert(0 <= terminal[i] && terminal[i] < N);
		dp[1 << i][terminal[i]] = 0;
	}
	std::priority_queue<std::pair<T, int>, 
		std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> pq;
	for(int S = 1; S < (1 << t); S++){
		for(int v = 0; v < N; v++){
			for(int U = S & (S - 1); U > 0; U = (U - 1) & S){
				dp[S][v] = std::min(dp[S][v], dp[U][v] + dp[U ^ S][v]);
			}
		}
		for(int v = 0; v < N; v++) pq.emplace(dp[S][v], v);
		while(!pq.empty()){
			auto [d, v] = pq.top();
			pq.pop();
			if(d > dp[S][v])continue;
			for(auto &&[u, w] : G[v]){
				if(d + w >= dp[S][u]) continue;
				dp[S][u] = d + w;
				pq.emplace(dp[S][u], u);
			}
		}
	}
	return dp.back();
}

#line 1 "Graph/steiner_tree.hpp"
template <class T> std::vector<T> steiner_tree(std::vector<std::vector<std::pair<int, T>>> &G, 
								std::vector<int> &terminal){
    const int N = G.size(), t = terminal.size();
	if(t == 0) {
		std::vector<T> ans(N);
		return ans;
	}
	std::vector<std::vector<T>> dp(1 << t, std::vector<T>(N, std::numeric_limits<T>::max() / 2));
	for(int i = 0; i < t; i++){
		assert(0 <= terminal[i] && terminal[i] < N);
		dp[1 << i][terminal[i]] = 0;
	}
	std::priority_queue<std::pair<T, int>, 
		std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> pq;
	for(int S = 1; S < (1 << t); S++){
		for(int v = 0; v < N; v++){
			for(int U = S & (S - 1); U > 0; U = (U - 1) & S){
				dp[S][v] = std::min(dp[S][v], dp[U][v] + dp[U ^ S][v]);
			}
		}
		for(int v = 0; v < N; v++) pq.emplace(dp[S][v], v);
		while(!pq.empty()){
			auto [d, v] = pq.top();
			pq.pop();
			if(d > dp[S][v])continue;
			for(auto &&[u, w] : G[v]){
				if(d + w >= dp[S][u]) continue;
				dp[S][u] = d + w;
				pq.emplace(dp[S][u], u);
			}
		}
	}
	return dp.back();
}

Back to top page