题意：给你n,m,k ，分别表示有n个点，m条边，每条边有一个权值，表示修复这条边需要的代价，从前k个点中任取一个使其和后k个点中的某一个点，通过边连接，并且必须是一一对应，问最小的代价是多少。

解法：看到某些点必须选并使其联通，所以想到了斯坦纳树，但是需要注意的是这道题是让k 对点满足一一对应的联通关系，也就是说最后生成的不一定是一颗，而有可能是一片森林。那么我们可以先按照斯坦纳树的方式来进行DP，求出所有的状态，然后再进行一次状压dp，dp[sta]=min(dp[sta],dp[s]+dp[sta-s])，用两棵树表示当前状态。不会斯坦纳树可以去学习一下。


#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, k;
int head[5010], edgecnt;
int dp[53][(1<<11)],mi[20],vis[5010],dp2[(1<<11)];
struct edge{
    int to,next,len;
}E[5010];
queue <int> pq;
void init(){
    edgecnt=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){
    E[edgecnt].to=v,E[edgecnt].len=w,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
void spfa(int sta){
    while(!pq.empty()){
        int now = pq.top(); pq.pop();
        for(int i=head[now]; ~i; i=E[i].next){
            if(dp[E[i].to][sta]>dp[now][sta]+E[i].len){
                dp[E[i].to][sta] = dp[now][sta]+E[i].len;
                if(!vis[E[i].to]){
                    vis[E[i].to] = 1;
                    pq.push(E[i].to);
                }
            }
        }
        vis[now]=0;
    }
}
bool check(int sta){
    int ans = 0;
    for(int i=0; i<k; i++){
        if(sta&(1<<i)) ans++;
        if(sta&(1<<(i+k))) ans--;
    }
    return (ans==0);
}

int main(){
    int T;
    scanf("%d", &T);
    mi[0] = 1;
    for(int i=1; i<11; i++) mi[i] = mi[i-1]*2;
    while(T--){
        while(!pq.empty()) pq.pop();
        init();
        scanf("%d %d %d", &n,&m,&k);
        for(int i=1; i<=m; i++){
            int x, y, z;
            scanf("%d %d %d", &x,&y,&z);
            add(x, y, z);
            add(y, x, z);
        }
        for(int i=1; i<=n; i++)
            for(int j=0; j<mi[10]; j++)
                dp[i][j] = inf;
        for(int i=1; i<=k; i++) dp[i][mi[i-1]] = 0;
        int t = k;
        for(int i=n-k+1; i<=n; i++) dp[i][mi[t]] = 0, t++;
        for(int sta=1; sta<mi[t]; sta++){
            for(int i=1; i<=n; i++){
                for(int s=sta&(sta-1);s;s=sta&(s-1)){
                    int tt = dp[i][sta-s]+dp[i][s];
                    dp[i][sta]=min(dp[i][sta],tt);
                }
                if(dp[i][sta]!=inf) pq.push(i), vis[1]=1;
            }
            spfa(sta);
        }
        for(int sta=1;sta<mi[t];sta++){
            dp2[sta]=inf;
            for(int i=1; i<=n; i++) dp2[sta]=min(dp2[sta], dp[i][sta]);
        }
        for(int sta=1;sta<mi[t];sta++)
            if(check(sta))
                for(int s=sta&(sta-1);s;s=sta&(s-1))
                    if(check(s))
                        dp2[sta]=min(dp2[sta], dp2[s]+dp2[sta-s]);
        if(dp2[mi[t]-1]==inf) puts("No solution");
        else printf("%d\n", dp2[mi[t]-1]);
    }
    return 0;
}