斯坦纳树

一个带权无向图$G(V,E)$上，令点集$V'\subseteq V$为关键点集，要联通所有关键点最小的代价。

该问题为公认的NPC问题，目前没有找到多项式复杂度的解！

以下算法只能解决关键点数较少时的问题$\mid V'\mid \le 20$

洛谷 P6192

给定一个包含 $n$ 个结点和 $m$ 条带权边的无向连通图 $G=(V, E)$ 再给定包含 $k$ 个结点的点集 $S,$ 选出 $G$ 的子图 $G^{\prime}=\left(V^{\prime}, E^{\prime}\right),$ 使得:

1. $S \subseteq V^{\prime}$

2. $G^{\prime}$ 为连通图;

3. $E^{\prime}$ 中所有边的权值和最小。

你只需要求出 $E^{\prime}$ 中所有边的权值和。

保证给出的无向图连通，但可能存在重边和自环。

解法

显然最后得出的图一定是一颗树

记$dp[S'][i]$为以$i$为根，联通点集$S'$的最小代价，则有一下两种转移方式

1. $dp[S'][i]=dp[T][i]+dp[S'-T][i]$，缩小问题范围
2. $dp[S'][i]=dp[S'][j]+dist(i,j)$

遍历集合$S'\subseteq S$，对于每一个子集$s$，先进行第一类转移，再进行第二类转移。

AC代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<int, int>  
#define sqr(x) ((x)*(x))
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;
int n, m, k;
int st[maxn];
int dp[(1<<10) + 100][maxn];
vector<pii> G[maxn];

void dijkstra(int s){
    priority_queue<pii, vector<pii>, greater<pii> > que;
    for(int i=1; i<=n; i++) {
        if(dp[s][i] != inf) que.push({dp[s][i], i});
    }
    while(!que.empty()){
        pii cur = que.top(); que.pop();
        int u = cur.second;
        if(dp[s][u] != cur.first) continue;
        for(pii edge:G[u]){
            int v = edge.first;
            if(dp[s][v] > dp[s][u] + edge.second){
                dp[s][v] = dp[s][u] + edge.second;
                que.push({dp[s][v], v});
            }
        }
    }
}

void solve(){
    memset(dp, 0x3f, sizeof dp);

    cin >> n >> m >> k;
    for(int i=0, u, v, w; i<m; i++){
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    for(int i=0; i<k; i++) cin >> st[i];

    for(int i=0; i<k; i++)
        dp[1<<i][st[i]] = 0;
    
    for(int s=1; s<(1<<k); s++){ 
        for(int subs = s&(s-1); subs; subs = s & (subs-1)){ // 第二类转移
            for(int i=1; i<=n; i++){
                dp[s][i] = min(dp[s][i], dp[subs][i] + dp[subs ^ s][i]);
            }
        }
        dijkstra(s); // 第一类转移
    }
    cout << dp[(1<<k)-1][st[rand() % k]] << '\n';
}

signed main(){
    Android;
    solve();
}