D3

Steiner Tree

Template : Here
Process :

1. Connected Points : K = (01…10)_2
2. For every node i and state K : f(i, K) := min. sum of edges connect points in K
3. dp1 : f(i, K) = \min(f(i, K), f(i, K’)+f(i, K-K’))
4. dp2 : f(i, K) = \min(f(i, K), f(j, K)+w(i, j))
5. Ans : f(T_0, 2^{N_k}-1)

Template Code :

#include 
using namespace std;

map G;
map emp;
vector Vks;
queue Q;

vector relax(vector dp, long long cur) {
    set vis;
    while (!Q.empty()) {
        pair c = Q.front();Q.pop();
        if (vis.find(c.second)!=vis.end()) continue;
        vis.insert(c.second);
        for (map::iterator it=G[c.second].begin();it!=G[c.second].end();it++) {
            if (dp[(*it).first][cur] > dp[c.second][cur] + (*it).second) {
                dp[(*it).first][cur] = dp[c.second][cur] + (*it).second;
                Q.push(make_pair(dp[(*it).first][cur], (*it).first));
            }
        }
    }
    return dp;
}

int main() {
    long long V, E, Vk;cin >> V >> E >> Vk;
    vector dp;
    vector empV(1 X;X--;
        Vks.push_back(X);
        dp[X][1<<i] = 0;
    }
    for (long long cur=1;cur<(1<<Vk);cur++) {
        for (long long i=0;i<V;i++) {
            for (long long sub = cur&(cur-1);sub;sub=cur&(sub-1)) {
                dp[i][cur] = min(dp[i][cur], dp[i][sub]+dp[i][cur^sub]);
            } 
            if (dp[i][cur]!=INT_MAX) Q.push(make_pair(dp[i][cur],i));
        }
        dp = relax(dp, cur);
    }
    cout << dp[Vks[0]][(1<<Vk)-1];
    return 0;
}

Tables :
Steiner Tree – Problems