题目链接 题目描述 小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。该部门有 n n n 个情报站，用 1 1 1 到 n n n 的整数编号。给出 m m m 对情报站 u i , v i u_i,v_i ui,vi 和费用 w i w_i wi，表示情报站 u i u_i ui 和 v i v_i vi 之间可以花费 w i w_i wi 单位资源建立通道。
如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就建立了通道连接。形式化地，若 u i ui ui 和 v i vi vi 建立了通道，那么它们建立了通道连接；若 u i u_i ui 和 v i v_i vi 均与 t i t_i ti 建立了通道连接，那么 u i u_i ui 和 v i v_i vi 也建立了通道连接。
现在在所有的情报站中，有 p p p 个重要情报站，其中每个情报站有一个特定的频道。小铭铭面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。
输入格式 第一行包含三个整数 n , m , p n,m,p n,m,p，表示情报站的数量，可以建立的通道数量和重要情报站的数量。
接下来 m m m 行，每行包含三个整数 u i , v i , w i u_i,v_i,w_i ui,vi,wi，表示可以建立的通道。最后有 p p p 行，每行包含两个整数 c i , d i c_i,d_i ci,di，表示重要情报站的频道和情报站的编号。
输出格式 输出一行一个整数，表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。
输入输出样例 输入 #1
5 8 4 1 2 3 1 3 2 1 5 1 2 4 2 2 5 1 3 4 3 3 5 1 4 5 1 1 1 1 2 2 3 2 4输出 #1
4说明/提示 选择 ( 1 ; 5 ) , ( 3 ; 5 ) , ( 2 ; 5 ) , ( 4 ; 5 ) (1; 5), (3; 5), (2; 5), (4; 5) (1;5),(3;5),(2;5),(4;5) 这 4 4 4 对情报站连接。
对于 100 % 100\% 100% 的数据， 0 < c i ≤ p ≤ 10 0 <c_i \le p \le 10 0<ci≤p≤10; 0 < u i , v i , d i ≤ n ≤ 1000 0 <u_i,v_i,d_i \le n \le 1000 0<ui,vi,di≤n≤1000; 0 ≤ m ≤ 3000 0 \le m \le 3000 0≤m≤3000; 0 ≤ w i ≤ 20000 0 \le w_i \le 20000 0≤wi≤20000。 这道题将关键节点划分成多个种类，要求相同种类的连通，不同种类的关键节点生成树可以共用边。
这里需要在求斯坦纳树的基础上二次dp。
设 a n s [ s ] ans[s] ans[s] 表示保证点集 s s s 中相同种类的关键节点连通所需的最小边权和。这里的点集 s s s 要保证对于在这个点集中的某一类点，所有这个种类的点都要在这个点集中。
转移方程为： a n s [ s ] = { min t ⊆ s ( a n s [ s ] , a n s [ t ] + a n s [ s − t ] ) min 1 ≤ i ≤ n ( a n s [ s ] , d p [ i ] [ s ] ) ans[s]=\left\{\begin{matrix} \min\limits_{t\subseteq s}(ans[s],ans[t]+ans[s-t])\\ \min\limits_{1\le i\le n}(ans[s],dp[i][s]) \end{matrix}\right. ans[s]={t⊆smin(ans[s],ans[t]+ans[s−t])1≤i≤nmin(ans[s],dp[i][s]) 洛谷卡常严重，开O2才能过，loj可正常过。
#include<bits/stdc++.h> #define pb push_back #define INF 0x3f3f3f3f using namespace std; inline int qr() { int f = 0, fu = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-')fu = -1; c = getchar(); } while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + c - 48; c = getchar(); } return f * fu; } const int N = 1005, M = 3005; int n, m, k; int head[N], ver[M << 1], edge[M << 1], Next[M << 1], tot; int dp[N][1 << 10], key[11], ans[1 << 10], id[11]; bool v[N], ks[1 << 10]; vector<int> S, p; struct node { int d, x; inline bool operator<(node a) const { return d > a.d; } }; priority_queue<node> q; inline void add(int x, int y, int z) { ver[++tot] = y; edge[tot] = z; Next[tot] = head[x]; head[x] = tot; } inline void dijkstra(int s) { memset(v, false, sizeof(bool) * (n + 1)); while (!q.empty()) { node t = q.top(); q.pop(); if (v[t.x])continue; v[t.x] = true; for (register int i = head[t.x]; i; i = Next[i]) if (dp[ver[i]][s] > dp[t.x][s] + edge[i]) { dp[ver[i]][s] = dp[t.x][s] + edge[i]; q.push({dp[ver[i]][s], ver[i]}); } } } int main() { memset(dp, 0x3f, sizeof(dp)); n = qr(), m = qr(), k = qr(); for (register int i = 1; i <= m; i++) { int x = qr(), y = qr(), z = qr(); add(x, y, z), add(y, x, z); } int kd = 0; for (register int i = 1; i <= k; i++) { int c = qr(), d = qr(); kd = max(kd, c), id[c] = d; dp[d][1 << (i - 1)] = 0; key[c] |= 1 << (i - 1); } for (register int s = 1; s < (1 << k); s++) { for (register int i = 1; i <= n; i++) { for (register int t = s & (s - 1); t; t = s & (t - 1)) dp[i][s] = min(dp[i][s], dp[i][t] + dp[i][s ^ t]); if (dp[i][s] != INF)q.push({dp[i][s], i}); } dijkstra(s); } for (register int i = 1; i < (1 << kd); i++) { int rs = 0, rp; for (int j = i, c = 1; j; j >>= 1, c++)if (j & 1)rs |= key[c], rp = id[c]; p.pb(rp), S.pb(rs), ks[rs] = true; } memset(ans, 0x3f, sizeof(int) * (1 << k)); int len = S.size(); for (register int i = 0, s; i < len; i++) { s = S[i], ans[s] = min(ans[s], dp[p[i]][s]); for (register int t = s & (s - 1); t; t = s & (t - 1)) if (ks[t])ans[s] = min(ans[s], ans[t] + ans[t ^ s]); } printf("%d\n", ans[(1 << k) - 1]); return 0; }