本文共 1091 字，大约阅读时间需要 3 分钟。

假如没有特殊点只能连出一条边的限制就是个裸的斯坦纳树了

斯坦纳树有两个转移,其中转移

$$f[i][s]=\min \{$$

这就是合并两个子树,所以我们不对特殊点做这个转移即可

#include 
   
    using namespace std;const int maxn = 1e4+10;const int inf = 1e9;double x[maxn],y[maxn];double f[maxn][1<<11];int vis[maxn],n,k;struct edge{
   	int to,nxt; double w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,double w){
   	d[++cnt] = ( edge ){
   v,head[u],w},head[u] = cnt;}double di(int i,int j){
   	return sqrt( ( y[i]-y[j] )*(y[i]-y[j] )+( x[i]-x[j] )*(x[i]-x[j]) );}queue
    
     q;void spfa(int s){
   	while( !q.empty() )	{
   		int u = q.front(); q.pop();		vis[u] = 0;		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( f[v][s]>f[u][s]+d[i].w )			{
   				f[v][s] = f[u][s]+d[i].w;				if( !vis[v] )	q.push( v ),vis[v] = 1;			}		}	}}int main(){
   	cin >> n >> k;	for(int i=1;i<=n;i++)		cin >> x[i] >> y[i];	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)		if( i!=j )	add( i,j,di(i,j) );	for(int i=0;i<=n;i++)	for(int j=0;j<=(1<
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116330944 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！