說到斯坦納樹問題，它是一種組合優(yōu)化問題，與最小生成樹相似，是最短網(wǎng)絡(luò)的一種。最小生成樹是在給定的點(diǎn)集和邊中尋求最短網(wǎng)絡(luò)使所有點(diǎn)連通。而最小斯坦納樹允許在給定點(diǎn)外增加額外的點(diǎn)，使生成的最短網(wǎng)絡(luò)開銷最小。

一、斯坦納樹

斯坦納樹問題是組合優(yōu)化問題，與最小生成樹相似，是最短網(wǎng)絡(luò)的一種，其實(shí)最小生成樹是最小斯坦納樹的一種特殊情況，最小生成樹是在給定的點(diǎn)集和邊中尋求最短網(wǎng)絡(luò)使所有點(diǎn)連通，而最小斯坦納樹允許在給定點(diǎn)外增加額外的點(diǎn)，使生成的最短網(wǎng)絡(luò)開銷最小。

二、問題的提出

平原上的三個(gè)城鎮(zhèn)間要興建一個(gè)公用的煤氣供應(yīng)站，在選址問題上，要考慮的主要問題是使由供應(yīng)站到三個(gè)城鎮(zhèn)的輸送管道的總長(zhǎng)最短。如何去尋找合適地點(diǎn)？

假若要建的是一個(gè)垃圾處理站，要修建三條公路將垃圾站與三個(gè)城鎮(zhèn)連起來。這時(shí)，因?yàn)槿齻€(gè)城鎮(zhèn)的居民的數(shù)目或工業(yè)性質(zhì)等的不同，每天運(yùn)送垃圾使用的車輛數(shù)目 各不相同，運(yùn)輸?shù)馁M(fèi)用也就各異。因此，選取地點(diǎn)時(shí)，如果仍考慮使三條公路的總長(zhǎng)最小，就不合理了。

這時(shí)應(yīng)該考慮：先計(jì)算出三個(gè)城鎮(zhèn)單位時(shí)間內(nèi)生產(chǎn)的垃圾數(shù)量的百分比（或每日運(yùn)輸費(fèi)用的百分比），如何選取地點(diǎn)，使得每個(gè)城鎮(zhèn)垃圾運(yùn)輸數(shù)量與公路里程的乘積之和為最小。

1638年，法國(guó)數(shù)學(xué)家費(fèi)馬在他所寫的一本關(guān)于求極值的書中就有了第一個(gè)問題，稱為費(fèi)馬問題

第二個(gè)問題則到了18世紀(jì)中葉才由辛普森（A.R.Simpson）提出來。

三、性質(zhì)

Pollak?Gilbert猜想：

平面上任意n點(diǎn)集，斯坦納最小樹長(zhǎng)與最小生成樹之長(zhǎng)的比值的最小值是

四、求解

這個(gè)問題比較現(xiàn)實(shí)，沒有太多需要解釋的地方

我們直接看解決方法：

首先我們知道，最優(yōu)解必然是一棵樹，這棵樹又是由若干棵子樹合并成的；

于是我們可以狀態(tài)壓縮，把 k 個(gè)節(jié)點(diǎn)的連通狀態(tài)用一個(gè)二進(jìn)制數(shù) j 表示；

dp[i][j]表示以 i 為根，與對(duì)應(yīng)狀態(tài)為 j 的節(jié)點(diǎn)連通的子樹的最小權(quán)值。

有兩種轉(zhuǎn)移方法：

枚舉子樹的形態(tài)：dp[i][j]=min(dp[i][j]，dp[i][k]+dp[i][l])，其中 k 和 l 是對(duì)j的一個(gè)劃分

按照邊進(jìn)行松弛：dp[i][j]=min(dp[i][j]，dp[i′][j]+w[i][i′])，其中 i 和 i′ 之間有邊相連

對(duì)于第一種轉(zhuǎn)移，我們直接枚舉子集就行了

對(duì)于第二種轉(zhuǎn)移，我們仔細(xì)觀察可以發(fā)現(xiàn)這個(gè)方程和最短路的約束條件是很類似的，于是我們可以用spfa或者dijkstra來進(jìn)行狀態(tài)轉(zhuǎn)移

枚舉子集的復(fù)雜度，spfa的復(fù)雜度為

所以總復(fù)雜度為

五、實(shí)例

給定一個(gè)包含個(gè)結(jié)點(diǎn)和條帶權(quán)邊的無向連通圖。

再給定包含個(gè)結(jié)點(diǎn)的點(diǎn)集，選出的子圖，使得：

1. 

2. 為連通圖；

3. 中所有邊的權(quán)值和最小。

你只需要求出中所有邊的權(quán)值和。

輸入格式

第一行：三個(gè)整數(shù)，表示的結(jié)點(diǎn)數(shù)、邊數(shù)和的大小。

接下來行：每行三個(gè)整數(shù)，表示編號(hào)為的點(diǎn)之間有一條權(quán)值為的無向邊。

接下來一行：個(gè)互不相同的正整數(shù)，表示的元素。

輸出格式

第一行：一個(gè)整數(shù)，表示中邊權(quán)和的最小值。

輸入輸出樣例

說明/提示

【樣例解釋】

樣例中給出的圖如下圖所示，紅色點(diǎn)為中的元素，紅色邊為的元素，此時(shí)中所有邊的權(quán)值和為 2+2+3+4=11，達(dá)到最小值。

【數(shù)據(jù)范圍】

對(duì)于 100% 的數(shù)據(jù)，1≤≤100,  1≤≤500,  1≤≤10,  1≤,v≤,  1≤≤ 。

保證給出的無向圖連通，但可能存在重邊和自環(huán)。

參考代碼如下：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 110
#define maxk 10
#define maxe 1010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
}
struct Graph
{
    int etot, head[maxn], to[maxe], next[maxe], w[maxe];
    void clear(int N)
    {
        for(int i=1;i<=N;i++)head[i]=0;
        etot=0;
    }
    void adde(int a, int b, int c=0){to[++etot]=b;w[etot]=c;next[etot]=head[a];head[a]=etot;}
    #define forp(_,__) for(auto p=__.head[_];p;p=__.next[p])
}G;
ll f[maxn][(1ll<<maxk)+10], n, m, k;
void dijkstra(ll s)
{
    priority_queue<pll,vector<pll>,greater<pll>> heap;
    ll i;
    rep(i,1,n)if(f[i][s]<linf)heap.em(pll(f[i][s],i));
    while(!heap.empty())
    {
        auto pr = heap.top(); heap.pop();
        if(pr.first!=f[pr.second][s])continue;
        forp(pr.second,G)
        {
            ll to = G.to[p];
            if(pr.first + G.w[p] < f[to][s])
            {
                f[to][s] = pr.first + G.w[p];
                heap.em( pll(f[to][s],to) );
            }
        }
    }
}
ll p[maxn];
int main()
{
    ll i, s, sub;
    n = read(), m = read(), k = read();
    rep(i,1,m)
    {
        ll u=read(), v=read(), w=read();
        G.adde(u,v,w);
        G.adde(v,u,w);
    }
    rep(i,1,n)rep(s,0,(1<<k)-1)f[i][s]=linf;
    rep(i,1,k)
    {
        p[i]=read();
        f[p[i]][1<<i-1]=0;
    }
    rep(s,0,(1<<k)-1)
    {
        rep(i,1,n)
            for(sub=s&(s-1);sub;sub=s&(sub-1))
                f[i][s] = min( f[i][s], f[i][sub] + f[i][s^sub] );
        dijkstra(s);
    }
    ll ans=linf;
    rep(i,1,n)ans=min(ans,f[i][(1<<k)-1]);
    printf("%lld",ans);
    return 0;
}