https://cn.vjudge.net/problem/HDU-4085
给你n,m,k ，分别表示有n个点，m条边，每条边有一个权值，表示修复这条边需要的代价
从前k个点中任取一个使其和后k个点中的某一个点，通过边连接，并且必须是一一对应，问最小的代价是多少。
先用斯坦纳树模板求出f[i][1<<k] 然后用dp[i]表示所有点为根的情况下连通状态为i的最小花费
这样我们就可以从1dp到1<<k得到答案 注意dp之前要先判总状态是否合法 再判子集是否合法 最后再进行dp更新
#include<bits/stdc++.h> #define N 6003 #define inf 1000000000 using namespace std; int n, m, k, tot; int point[N], next1[N], v[N], len[N]; int f[53][(1 << 11)], mi[20], can[N], dp[(1 << 11)]; queue<int> p; void add(int x, int y, int z) {tot++;next1[tot] = point[x];point[x] = tot;v[tot] = y;len[tot] = z;tot++;next1[tot] = point[y];point[y] = tot;v[tot] = x;len[tot] = z; } void spfa(int sta) {while (!p.empty()) {int now = p.front();p.pop();for (int i = point[now]; i; i = next1[i]) {if (f[v[i]][sta] > f[now][sta] + len[i]) {f[v[i]][sta] = f[now][sta] + len[i];if (!can[v[i]]) {can[v[i]] = 1;p.push(v[i]);}}}can[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;for (int T = 1; T <= t; T++) {scanf("%d%d%d", &n, &m, &k);tot = 0;memset(point, 0, sizeof(point));memset(next1, 0, sizeof(next1));for (int i = 1; i <= m; i++) {int x, y, z;scanf("%d%d%d", &x, &y, &z);add(x, y, z);}for (int i = 1; i <= n; i++)for (int j = 0; j < mi[10]; j++)f[i][j] = inf;for (int i = 1; i <= k; i++)f[i][mi[i - 1]] = 0;int t = k;for (int i = n - k + 1; i <= n; i++)f[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 t = f[i][sta - s] + f[i][s];f[i][sta] = min(f[i][sta], t);}if (f[i][sta] != inf)p.push(i), can[i] = 1;}spfa(sta);}for (int sta = 1; sta < mi[t]; sta++) {dp[sta] = inf;for (int i = 1; i <= n; i++)dp[sta] = min(dp[sta], f[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))dp[sta] = min(dp[sta], dp[s] + dp[sta - s]);if (dp[mi[t] - 1] == inf)printf("No solution\n");elseprintf("%d\n", dp[mi[t] - 1]);} }