Steiner Tree (シュタイナー木)
(lib/graph/steiner_tree.hpp)

• View this file on GitHub
• Last update: 2024-10-31 23:51:11+09:00
• Include: #include "lib/graph/steiner_tree.hpp"
• Link: https://www.slideshare.net/wata_orz/ss-12131479

Steiner Tree (シュタイナー木)

概要

重みがついたグラフに対して最小シュタイナー木のコストを求めます。

使い方

• SteinerTree(node_size): コンストラクタ (node_size は頂点数)
• add_edge(u, v, cost): 頂点 $u$ から 頂点 $v$ に重み cost の無向辺を追加します。
• build(terminal): ターミナルを terminal として、最小シュタイナー木のコストの計算を行います。
• get(i): ターミナルに加えて、頂点 $i$ を含んだ最小シュタイナー木のコストを求めます。(-1 の場合は何も含まない)

計算量

頂点数を $V$、辺の数を $E$、ターミナルの数を $t$ とすると、$\mathrm{O}(V 3^t + (V + E) 2^t \log V)$

Code

#pragma once

/**
 * @brief Steiner Tree (シュタイナー木)
 * @docs docs/graph/steiner_tree.md
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */

template <typename T>
struct SteinerTree{
private:
    int V, t;
    vector<int> last_terminal;
    vector<vector<array<T, 2>>> G;
    vector<vector<T>> dp;
    const T INF = numeric_limits<T>::max() / 3;
    using PP = pair<T, int>;

public:
    SteinerTree(int node_size) : V(node_size), G(V){}

    void add_edge(int u, int v, T cost){
        G[u].push_back({v, cost}), G[v].push_back({u, cost});
    }

    void build(vector<int> &terminal){
        t = (int) terminal.size();
        last_terminal = terminal;
        if(t == 0) return;
        dp.resize((1 << t), vector<T>(V, INF));
        for(int i = 0; i < t; i++){
            dp[(1 << i)][terminal[i]] = 0;
        }
        for(int i = 1; i < (1 << t); i++){
            for(int j = 0; j < V; j++){
                // subset
                for(int k = i; k > 0; k = (k - 1) & i){
                    dp[i][j] = min(dp[i][j], dp[k][j] + dp[i ^ k][j]);
                }
            }

            priority_queue<PP, vector<PP>, greater<PP>> que;
            for(int j = 0; j < V; j++){
                que.emplace(dp[i][j], j);
            }

            while(!que.empty()){
                PP p = que.top();
                que.pop();
                int v = p.second;
                if(dp[i][v] < p.first) continue;
                for(auto &[to, cost] : G[v]){
                    if(dp[i][to] > dp[i][v] + cost){
                        dp[i][to] = dp[i][v] + cost;
                        que.emplace(dp[i][to], to);
                    }
                }
            }
        }
    }

    T get(int i = -1){
        if(i == -1) return dp[(1 << t) - 1][last_terminal[0]];
        return dp[(1 << t) - 1][i];
    }
};

#line 2 "lib/graph/steiner_tree.hpp"

/**
 * @brief Steiner Tree (シュタイナー木)
 * @docs docs/graph/steiner_tree.md
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */

template <typename T>
struct SteinerTree{
private:
    int V, t;
    vector<int> last_terminal;
    vector<vector<array<T, 2>>> G;
    vector<vector<T>> dp;
    const T INF = numeric_limits<T>::max() / 3;
    using PP = pair<T, int>;

public:
    SteinerTree(int node_size) : V(node_size), G(V){}

    void add_edge(int u, int v, T cost){
        G[u].push_back({v, cost}), G[v].push_back({u, cost});
    }

    void build(vector<int> &terminal){
        t = (int) terminal.size();
        last_terminal = terminal;
        if(t == 0) return;
        dp.resize((1 << t), vector<T>(V, INF));
        for(int i = 0; i < t; i++){
            dp[(1 << i)][terminal[i]] = 0;
        }
        for(int i = 1; i < (1 << t); i++){
            for(int j = 0; j < V; j++){
                // subset
                for(int k = i; k > 0; k = (k - 1) & i){
                    dp[i][j] = min(dp[i][j], dp[k][j] + dp[i ^ k][j]);
                }
            }

            priority_queue<PP, vector<PP>, greater<PP>> que;
            for(int j = 0; j < V; j++){
                que.emplace(dp[i][j], j);
            }

            while(!que.empty()){
                PP p = que.top();
                que.pop();
                int v = p.second;
                if(dp[i][v] < p.first) continue;
                for(auto &[to, cost] : G[v]){
                    if(dp[i][to] > dp[i][v] + cost){
                        dp[i][to] = dp[i][v] + cost;
                        que.emplace(dp[i][to], to);
                    }
                }
            }
        }
    }

    T get(int i = -1){
        if(i == -1) return dp[(1 << t) - 1][last_terminal[0]];
        return dp[(1 << t) - 1][i];
    }
};

Back to top page