【题意】:给定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<intint> 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, falsesizeof(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