题意

给出n个点的完全图，另外还有一个点，向其中的m个点连有向边。求至少包含这个点和m个点的最小连通图，并输出最小的边权和。

分析

首先，问题是求最小边集，边的有向无向其实不重要，所以从单独的点连向m个点的那些有向边，可以直接看成无向边，因此单独的点和那m个点是完全相同的，不用再单独考虑；
问题转化为：已知N个点M条无向带权边，求一个最小连通图，必须包含其中的K个特殊点。因为要边权的花费最小，所以图中是不应该出现环的，最小连通图一定是一棵树。具有这样性质的树，被定义为斯坦纳树。
斯坦纳树的求解貌似是一个NP问题，做法基本还是暴力，但是因为这道题数据量很小，所以是可做的。推荐一篇大佬分析斯坦纳树的博客。
因为特殊点最多只有11个，所以暴力搜可以从K入手，先大致生成K个点的一个生成树，再看能不能借用其他N-K个点形成的网络的一部分来降低花费。
具体地来说，把状态定义为$$$(i, (a_1a_2...a_k)_{bin})$$$，表示以$$$i$$$号节点为根的一棵树，$$$a_j$$$为1则表示$$$i$$$至少与第$$$j$$$个特殊点是连通的。
现在用$$$state$$$简记$$$(a_1a_2...a_k)_{bin}$$$，那么$$$dp[i][state]$$$记录状态$$$(i,state)$$$的最小花费，有下面两个转移方程：
$$$$$$
\begin{align}
& dp[i][state]=min_{substate\subset state}\{dp[i][substate]+dp[i][state-substate]\} \\
& dp[i][state]=min\{dp[i][state],dp[j][state]+w(i,j)\}
\end{align}
$$$$$$
对这块理解不是很到位，以下可能有不严谨之处。
第一层转移，对于固定的$$$i$$$，大的$$$state$$$的$$$dp$$$用$$$substate$$$的dp求出并取最小，相当于用两棵小的树可以合并成一棵大一点的树。
然后第二层转移，所有的生成树大致长什么样都知道了，但很可能还不是最优的，还要进一步减少花费。转移方程的形式其实很像求最短路的形式，对于固定的$$$state$$$，相当于把它们合并为一个新的点，并且就以这个点为起点，在新的图上跑一次最短路，也就是借用其他的点$$$j$$$对原来的边进行了松弛。
搜索完所有的状态以后，任意一个特殊点$$$X$$$，则$$$dp[X][{1...1}]$$$就是我们要求的斯坦纳树的最小花费。
比赛的时候想到的错误算法：

• 网络流：
  • 从单独的点出发->特殊点, 特殊点<->其他点, 特殊点->汇点）。
  • 错误原因：正解的流出量可以大于流入量，导致费用大的边也被选择，或者一条边对答案贡献多次。
• 缩边
• 找K个特殊点，两两之间的最短路，缩为一条边，构造新的图，求K个点的最小生成树
• 错误原因：特殊点之间的最短路可以分叉，缩边会对分叉前的公共部分重复计算。

代码

#include <stdio.h>

#include<queue>

#include<vector>

#include <memory.h>

using std::queue;

using std::vector;

/*

 *dp：

 *dp[i][st] 包含第i个点，且至少和state为1的关键点相连的最小花费

 *转移

 *dp[i][st]=Min{dp[i][st],dp[i][st-sub]+dp[i][sub]} 分解为两个

 *dp[i][st]=Min{dp[i][st],dp[j][st]+w(i,j)} i和j有边，关键点外面的部分spfa一下

 */

#define INF 0x3f3f3f3f

#define maxn 55

int g[maxn][maxn];

int dp[maxn][ << ];

queue<int> help;

int N,K;

int vis[maxn];

struct DeliveryCost {

    int u;

    int v;

    int cost;

};

void spfa(int cs){

    while(!help.empty())    {

        int id = help.front();help.pop();

        vis[id] = ;

        for(int i=;i<=N;++i){

            if (id == i || g[id][i] == INF)continue;

            if(dp[i][cs]>dp[id][cs]+g[id][i]){

                dp[i][cs] = dp[id][cs] + g[id][i];

                if(!vis[i]){

                    vis[i] = ; help.push(i);

                }

            }

        }

    }

}

int solve(int n,

    vector<DeliveryCost> cost_e,

    vector<int> employees,

    vector<int> cost_b) {

    /*********begin*********/

    memset(g, 0x3f, sizeof g);

    memset(dp, 0x3f, sizeof dp);

    //建图

    //员工到员工

    int sz = cost_e.size();

    int tu, tv, tc;

    for(int i=;i<sz;i++)    {

        tu = cost_e[i].u; tv = cost_e[i].v; tc = cost_e[i].cost;

        g[tu][tv] = tc;

        g[tv][tu] = tc;

    }

    //老板到特殊员工

    K = cost_b.size();

    for(int i=;i<K;i++)    {

        g[n + ][employees[i]] = cost_b[i];

        g[employees[i]][n+] = cost_b[i];

        dp[employees[i]][ << i] = ;

    }

    dp[n + ][ << K] = ;

    K++; N=n+;

    int limit = ( << K) - ;

    //第一层转移

    for(int sta=;sta<=limit;sta++)    {//遍历state

        for(int i=;i<=N;i++)    {

            for(int s=sta;s;s=(s-)&sta)    //遍历substate

                if(dp[i][s]+dp[i][sta-s]<dp[i][sta])

                    dp[i][sta] = dp[i][s] + dp[i][sta - s];

            if (dp[i][sta] < INF)    {//i-sta被松弛，放入队列

                help.push(i);

                vis[i] = ;

            }

        }

        //第二层转移

        spfa(sta);

    }

    //N是特殊点中的一个

    return dp[N][limit];

    /*********end*********/

}

int main(){

    //测试一下样例

    int n = ;

    vector<DeliveryCost>cost_e{ { , ,  },{ , ,  },{ , ,  } };

    vector<int> employees{ , };

    vector<int> cost_b{ , };

    printf("%d",solve(n, cost_e, employees, cost_b));

}

总结

虽然过了，还是来算一下复杂度吧
以每个点为根都有$$$2^k$$$个$$$state$$$，求解每一个都遍历了其所有$$$substate$$$。含$$$x$$$个$$$1$$$的state共$$$C_k^x$$$个，$$$substate$$$数量都是$$$2^x$$$，所以复杂度为
$$$$$$\begin{align}
& n\cdot\sum{C_k^x\cdot 2^x}\\
=& n\cdot\sum{C_k^x\cdot 1^{k-x}\cdot 2^x}\\
=& (1+2)^kn =3^kn
\end{align}$$$$$$
此外，对每个$$$state$$$，都要跑一遍$$$spfa$$$，因为是稠密图，如果按spfa的最坏情况来看就是:
$$$$$$\begin{align}
& 2^k\cdot O(spfa)\\
=& 2^k\cdot O(VE)\\
=& 2^k\cdot O(n\cdot \frac{n(n-1)}{2})\\
=& 2^k\cdot O(n^3)\\
\end{align}$$$$$$
最终复杂度为$$$O(3^kn+2^kn^3)=O(2^kn^3)$$$，大约在3e8左右，但是实际上很快，十组样例只跑了14.408秒，可能是因为$$$spfa$$$的复杂度只有$$$O(kE)$$$吧，也有可能是因为数据比较水233。