最小斯坦纳树

众所周知，斯坦纳树问题是一类特殊的生成树问题……

给定一个包含 $n$ 个结点和 $m$ 条带权边的无向连通图 $G=(V,E)$。
再给定包含 $k$ 个结点的点集 $S$，选出 $G$ 的子图 $G=(V,E)$，使得：

1. $S\subseteq V$；
2. $G$ 为连通图；
3. $E$ 中所有边的权值和最小。

你只需要求出 $E$ 中所有边的权值和。
$n\le 100, m\le 500, k\le 10$

上述问题被称作「最小斯坦纳树」问题。

设 $f[i,S]$ 表示当前在 $i$ ，$S$ 中的点已经连通的最小代价，则有转移：

$$ \begin{aligned} f[i,S] &=\min f[i,S_0]+f[i,S\oplus S_0]\newline f[i,S] &=\min f[j,S]+\text{sp}(i,j) \end{aligned} $$

容易发现后一个转移是最短路的形式，考虑到不存在负权边，使用 Dijkstra 转移，复杂度 $O(2^k n\log n)$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

const int CN = 101;
const int INF = 0x3f3f3f3f;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class fs {public: int to,nxt,w; void init(int t,int n,int d) {to = t, nxt = n, w = d;} } E[CN * CN];
int hd[CN], ecnt = 0; void add(int x,int y,int z) {E[++ecnt].init(y, hd[x], z); hd[x] = ecnt;}

int n, m, k, key[CN], f[CN][1 << 10];

class DJ {public: int id, v; bool operator < (const DJ & a) const {return v > a.v;}};
DJ make(int a, int b) {DJ c; c.id = a, c.v = b; return c;}
priority_queue<DJ> Q; bool vis[CN];
void sp(int S){
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++) if(f[i][S] < INF) Q.push( make(i, f[i][S]) );
    while(!Q.empty()){
        int u = Q.top().id; Q.pop();
        vis[u] = true;
        for(int k = hd[u]; k; k = E[k].nxt){
            int v = E[k].to; if(vis[v]) continue;
            if(f[v][S] > f[u][S] + E[k].w){
                f[v][S] = f[u][S] + E[k].w;
                Q.push( make(v, f[v][S]) );
            }
        }
    }
}

int main()
{
    freopen("_in.in", "r", stdin);

    n = read(), m = read(), k = read();
    while(m--){
        int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, w);
    }
    for(int i = 1; i <= k; i++) key[i] = read();

    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= k; i++) f[ key[i] ][ 1 << (i - 1) ] = 0;
    for(int i = 1; i <= n; i++) f[i][0] = 0;
    for(int S = 1; S < (1 << k); S++){
        for(int i = 1; i <= n; i++)
            for(int V = S; V; V = (V - 1) & S)
                f[i][S] = min(f[i][S], f[i][V] + f[i][S ^ V]);
        sp(S);
    }

    int ans = INF;
    for(int i = 1; i <= n; i++) ans = min(ans, f[i][(1 << k) - 1]);
    printf("%d", ans);
}