思路：
这里必须要选择的点是2*k个，首先就是求一边斯坦纳树，然后做一次动态规划出每个状态下的最小值。
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Maxn 210 #define Maxm 100010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 0x3f3f3f3f #define Mod 1000000007 using namespace std; int dp[Maxn][1<<13],dis[Maxn][Maxn],n,m,K,ans[1<<13]; void init() { memset(dp,63,sizeof(dp)); memset(dis,63,sizeof(dis)); memset(ans,63,sizeof(ans)); } void floyd() { int i,j,k; for(k=1;k<=n;k++){ dis[k][k]=0; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } } } bool Ok(int s) { int res=0; for(int i=0;s;i++,s>>=1) res+=(s&1)*(i<K?1:-1); return (res==0?true:false); } void solve() { int i,j,k; int N=1<<(2*K); N--; for(i=0;i<K;i++){ for(j=1;j<=n;j++){ dp[j][1<<i]=dis[i+1][j]; dp[j][1<<(K+i)]=dis[n-K+i+1][j]; } } for(i=1;i<=N;i++){ if((i&(i-1))==0) continue; for(j=1;j<=n;j++){ dp[j][i]=inf; for(k=(i-1)&i;k;k=(k-1)&i){ dp[j][i]=min(dp[j][i],dp[j][k]+dp[j][i-k]); } } for(j=1;j<=n;j++){ for(k=1;k<=n;k++){ dp[j][i]=min(dp[j][i],dp[k][i]+dis[j][k]); } } } for(i=1;i<=N;i++){ ans[i]=inf; for(j=1;j<=n;j++) ans[i]=min(ans[i],dp[j][i]); } for(i=0;i<=N;i++){ if(Ok(i)){ for(j=(i-1)&i;j;j=(j-1)&i){ if(Ok(j)){ ans[i]=min(ans[i],ans[j]+ans[i-j]); } } } } if(ans[N]>=inf) printf("No solution "); else printf("%d ",ans[N]); } int main() { int i,j,u,v,val,t; scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&m,&K); init(); for(i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&val); dis[u][v]=dis[v][u]=min(dis[u][v],val); } floyd(); solve(); } return 0; }