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

1. 什么是斯坦納樹？

斯坦納樹問題是組合優(yōu)化學科中的一個問題。將指定點集合中的所有點連通，且邊權(quán)總和最小的生成樹稱為最小斯坦納樹（Minimal Steiner Tree），其實最小生成樹是最小斯坦納樹的一種特殊情況。而斯坦納樹可以理解為使得指定集合中的點連通的樹，但不一定最小。

2. 如何求解最小斯坦納樹？

      可以用DP求解，dp[i][state]表示以i為根，指定集合中的點的連通狀態(tài)為state的生成樹的最小總權(quán)值。

      轉(zhuǎn)移方程有兩重：

      第一重，先通過連通狀態(tài)的子集進行轉(zhuǎn)移。

      dp[i][state]=min{ dp[i][subset1]+dp[i][subset2] } 

      枚舉子集的技巧可以用 for(sub=(state-1)&state;sub;sub=(sub-1)&state)。

      第二重，在當前枚舉的連通狀態(tài)下，對該連通狀態(tài)進行松弛操作。

      dp[i][state]=min{ dp[i][state], dp[j][state]+e[i][j] }

      為什么只需對該連通狀態(tài)進行松弛？因為更后面的連通狀態(tài)會由先前的連通狀態(tài)通過第一重轉(zhuǎn)移得到，所以無需對別的連通狀態(tài)松弛。松弛操作用SPFA即可。

復雜度 O(n*3^k+cE*2^k)

      c為SPFA復雜度中的常數(shù)，E為邊的數(shù)量，但幾乎達不到全部邊的數(shù)量，甚至非常小。3^k來自于子集的轉(zhuǎn)移sum{C(i,n)*2^i} (1≤i≤n)，用二項式展開求一下和。

代碼：

/*
 *  Steiner Tree：求，使得指定K個點連通的生成樹的最小總權(quán)值
 *  st[i] 表示頂點i的標記值，如果i是指定集合內(nèi)第m(0<=m<K)個點，則st[i]=1<<m 
 *  endSt=1<<K
 *  dptree[i][state] 表示以i為根，連通狀態(tài)為state的生成樹值
 */
#define CLR(x,a) memset(x,a,sizeof(x))
 
int dptree[N][1<<K],st[N],endSt;
bool vis[N][1<<K];
queue<int> que;
 
int input()
{
   /*
	*    輸入，并且返回指定集合元素個數(shù)K
	*    因為有時候元素個數(shù)需要通過輸入數(shù)據(jù)處理出來，所以單獨開個輸入函數(shù)。
    */
}
 
void initSteinerTree()
{
	CLR(dptree,-1);
	CLR(st,0);
	for(int i=1;i<=n;i++) CLR(vis[i],0);
	endSt=1<<input();
	for(int i=1;i<=n;i++)
		dptree[i][st[i]]=0;
}
 
void update(int &a,int x)
{
	a=(a>x || a==-1)? x : a;
}
 
void SPFA(int state)
{
	while(!que.empty()){
		int u=que.front();
		que.pop();
		vis[u][state]=false;
		for(int i=p[u];i!=-1;i=e[i].next){
			int v=e[i].vid;
			if(dptree[v][st[v]|state]==-1 || 
				dptree[v][st[v]|state]>dptree[u][state]+e[i].w){
 
			    dptree[v][st[v]|state]=dptree[u][state]+e[i].w;
				if(st[v]|state!=state || vis[v][state]) 
					continue; //只更新當前連通狀態(tài)
				vis[v][state]=true;
				que.push(v);
			}
		}
	}
}
 
void steinerTree()
{
	for(int j=1;j<endSt;j++){
		for(int i=1;i<=n;i++){
			if(st[i] && (st[i]&j)==0) continue;
			for(int sub=(j-1)&j;sub;sub=(sub-1)&j){
				int x=st[i]|sub,y=st[i]|(j-sub);
				if(dptree[i][x]!=-1 && dptree[i][y]!=-1)
					update(dptree[i][j],dptree[i][x]+dptree[i][y]);
			}
			if(dptree[i][j]!=-1) 
				que.push(i),vis[i][j]=true;
		}
		SPFA(j);
	}
}