【题意】：给定n(n<=5)个必选点，和m(m<=1000)个辅助点，每个点都有权值表示在这个点挖井的费用。还有p条边，每条边都有费用。问使得1-n个点都有水喝的最小费用是多少。
【题解】：显然最后求出来的解可能是一个森林。
设状态dp[i][j]表示在 i 挖井且连通了 j 这些点的最小费用。
状态minn[i]表示 i 这些点都有水喝的最小费用。
我的思路是用斯坦纳树求出所有dp[i][j]的值，然后再dp一次，求出minn[i]的值。ans = min[(1<<n)-1];
看到还有一种解法，就是加入一个虚拟结点，然后每个点都向虚拟结点连边，费用是每个结点挖井的费用。这样处理后就没有点权只有边权了，而且1-n号点最后一定是连通的，然后求一次斯坦纳树就可以了。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define maxn 1050
26 const int inf = 1 << 29;
27 struct Edge {
28 int v, w;
29 Edge(){}
30 Edge(int _v, int _w) {
31 v = _v, w = _w;
32 }
33 };
34 int n, m, p;
35 int dp[maxn][1<<5], minn[1<<5];
36 int val[maxn], hash[maxn];
37 bool visit[maxn][1<<5];
38 vector<Edge> vec[maxn];
39 queue<int> que;
40 void update(int cost, int v, int nst) {
41 if(cost < dp[v][nst]) {
42 dp[v][nst] = cost;
43 if(!visit[v][nst]) {
44 que.push(v + (nst << 10));
45 visit[v][nst] = true;
46 }
47 }
48 }
49
50 void solve() {
51 while(!que.empty()) que.pop();
52 memset(hash, 0, sizeof(hash));
53 memset(visit, false, sizeof(visit));
54 int nn = 1 << n;
55 for(int i = 0; i <= n + m; i++)
56 for(int j = 0; j < nn; j++)
57 dp[i][j] = inf;
58 for(int i = 1; i <= n; i++) {
59 hash[i] = 1 << (i - 1);
60 update(val[i], i, hash[i]);
61 }
62 while(!que.empty()) {
63 int now = que.front();
64 que.pop();
65 int u = now % (1 << 10), st = now >> 10;
66 visit[u][st] = false;
67 int size = vec[u].size();
68 for(int i = 0; i < size; i++) {
69 int v = vec[u][i].v, w = vec[u][i].w;
70 update(dp[u][st] + w - val[u] + val[v], v, st | hash[v]);
71 }
72 int t = nn - 1 - st;
73 for(int i = t; i; i = (i - 1) & t) {
74 update(dp[u][st] + dp[u][i|hash[u]] - val[u], u, st | i);
75 }
76 }
77 for(int i = 0; i < nn; i++) {
78 minn[i] = inf;
79 for(int j = 0; j <= n + m; j++)
80 minn[i] = min(minn[i], dp[j][i]);
81 }
82 for(int i = 0; i < nn; i++)
83 for(int j = i; j; j = (j - 1) & i)
84 minn[i] = min(minn[i], minn[i-j] + minn[j]);
85 printf("%d\n", minn[nn-1]);
86 }
87
88 int main() {
89 while(~scanf("%d%d%d", &n, &m, &p)) {
90 for(int i = 0; i < maxn; i++) vec[i].clear();
91 for(int i = 1; i <= n + m; i++) scanf("%d", &val[i]);
92 for(int i = 0; i < p; i++) {
93 int u, v, w;
94 scanf("%d%d%d", &u, &v, &w);
95 vec[u].pb(Edge(v, w));
96 vec[v].pb(Edge(u, w));
97 }
98 solve();
99 }
100 return 0;
101 }
102