题目链接：传送门

Description

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

Solution

又是一道斯坦纳树的题。还是一样的套路，只是最后在计算答案时要判断一下状态是否是前k个和后k个一一对应，跑个Dp即可

Code

    #include <bits/stdc++.h>

    using namespace std;

    const int Maxn = 50 + 5, Maxm = 6000 + 10, inf = 100000000;

    int N, M, K;
    int e, Begin[Maxm], To[Maxm * 2], Next[Maxm * 2], W[Maxm * 2];
    int Dis[Maxn][(1 << 11)], Vis[Maxm], Dp[(1 << 11)];

    inline void Init ()
    {
        e = 0;
        memset(Begin, 0, sizeof Begin);
        memset(Vis, 0, sizeof Vis);
    }

    inline void add_edge (int x, int y, int z)
    {
        To[++e] = y;
        Next[e] = Begin[x];
        Begin[x] = e;
        W[e] = z;
    }

    queue <int> Q;
    inline void SPFA (int state)
    {
        while (!Q.empty())
        {
            int x = Q.front(); Q.pop();
            Vis[x] = 0;
            for (int i = Begin[x]; i; i = Next[i])
            {
                int y = To[i];
                if (Dis[y][state] > Dis[x][state] + W[i])
                {
                    Dis[y][state] = Dis[x][state] + W[i];
                    if (!Vis[y])
                    {
                        Vis[y] = 1;
                        Q.push(y);
                    }
                }
            }
        }
    }

    inline int Check (int state)
    {
        int now = 0;
        for (int i = 0; i < K; ++i)
        {
            if (state & (1 << i)) ++now;
            if (state & (1 << (i + K))) --now;
        }
        return !now;
    }

    int main()
    {
    #ifdef hk_cnyali
        freopen("A.in", "r", stdin);
        freopen("A.out", "w", stdout);
    #endif
        int T;
        scanf("%d", &T);
        while (T--)
        {
            scanf("%d%d%d", &N, &M, &K);
            Init();
            while (M--)
            {
                int x, y, z;
                scanf("%d%d%d", &x, &y, &z);
                add_edge(x, y, z);
                add_edge(y, x, z);
            }

            for (int i = 1; i <= N; ++i)
                for (int j = 0; j < (1 << 10); ++j)
                    Dis[i][j] = inf;
            for (int i = 1; i <= K; ++i)
                Dis[i][1 << (i - 1)] = 0;
            int tmp = K;
            for (int i = N - K + 1; i <= N; ++i)
                Dis[i][1 << tmp] = 0, ++tmp;

            for (int state = 1; state < (1 << tmp); ++state)
            {
                for (int i = 1; i <= N; ++i)
                {
                    for (int s1 = state & (state - 1); s1; s1 = state & (s1 - 1))
                        Dis[i][state] = min(Dis[i][state], Dis[i][state - s1] + Dis[i][s1]);
                    if (Dis[i][state] != inf) Q.push(i), Vis[i] = 1;
                }
                SPFA(state);
            }

            for (int state = 1; state < (1 << tmp); ++state)
            {
                Dp[state] = inf;
                for (int i = 1; i <= N; ++i)
                    Dp[state] = min(Dp[state], Dis[i][state]);
            }

            for (int state = 1; state < (1 << tmp); ++state)
            {
                if (!Check(state)) continue;
                for (int s1 = state & (state - 1); s1; s1 = state & (s1 - 1))
                {
                    if (!Check(s1)) continue;
                    Dp[state] = min(Dp[state], Dp[s1] + Dp[state - s1]);
                }
            }
            if (Dp[(1 << tmp) - 1] == inf) cout<<"No solution"<<endl;
            else cout<<Dp[(1 << tmp) - 1]<<endl;
        }
        return 0;
    }