斯坦纳树

斯坦纳树是一类比较特殊的DP吧，主要针对点集连通问题，通常dp[i][s]表示以i为根的，连通状态为s的一棵树的最小权值，有两种转移方式，

其中state[i]表示点i的二进制标号，通常无关的点state值为0，

dp[i][s] = min{dp[i][s], dp[i][j] + dp[i][k]},这里是针对state[i]非0

dp[i][s] = min{dp[j][s] + dist(i, j), dp[i][s]},这里针对state[i]为0的点的转移方程。

更详细的分析在这里：http://endlesscount.blog.163.com/blog/static/821197872012525113427573/

UVALive 5717
Peach Blossom Spring

  1 //Template updates date: 20140316
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdio>
  5 #include <climits>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <cstring>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <stack>
 12 #include <set>
 13 #include <map>
 14 #include <cmath>
 15 #include <vector>
 16 #include <queue>
 17 #include <algorithm>
 18 #define  esp 1e-6
 19 #define  pi acos(-1.0)
 20 #define  inf 0x0f0f0f0f
 21 #define  pb push_back
 22 #define  lson l, m, rt<<1
 23 #define  rson m+1, r, rt<<1|1
 24 #define  lowbit(x) (x&(-x))
 25 #define  mp(a, b) make_pair((a), (b))
 26 #define  bit(k) (1<<(k))
 27 #define  in  freopen("solve_in.txt", "r", stdin);
 28 #define  out freopen("solve_out.txt", "w", stdout);
 29 
 30 #define  bug puts("********))))))");
 31 #define  inout in out
 32 
 33 #define  SET(a, v) memset(a, (v), sizeof(a))
 34 #define  SORT(a)   sort((a).begin(), (a).end())
 35 #define  REV(a)    reverse((a).begin(), (a).end())
 36 #define  READ(a, n) {REP(i, n) cin>>(a)[i];}
 37 #define  REP(i, n) for(int i = 0; i < (n); i++)
 38 #define  Rep(i, base, n) for(int i = base; i < n; i++)
 39 #define  REPS(s, i) for(int i = 0; s[i]; i++)
 40 #define  pf(x) ((x)*(x))
 41 #define  mod(n) ((n))
 42 #define  Log(a, b) (log((double)b)/log((double)a))
 43 #define Srand() srand((int)time(0))
 44 #define random(number) (rand()%number)
 45 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
 46 
 47 using namespace std;
 48 typedef long long  LL;
 49 typedef unsigned long long ULL;
 50 typedef vector<int> VI;
 51 typedef pair<int,int> PII;
 52 typedef vector<PII> VII;
 53 typedef vector<PII, int> VIII;
 54 typedef VI:: iterator IT;
 55 typedef map<string, int> Mps;
 56 typedef map<int, int> Mpi;
 57 typedef map<int, PII> Mpii;
 58 typedef map<PII, int> Mpiii;
 59 const int maxn = (1<<10);
 60 const int maxm = 50 + 10;
 61 int dp[maxm][maxn], ans[maxn], s[maxm];
 62 struct EDGE {
 63     int to, w;
 64     EDGE *next;
 65     EDGE() {}
 66     EDGE(int to, int w, EDGE *next):to(to), w(w), next(next) {}
 67 }*head[maxm], E[2000 + 10], *now;
 68 int n, m, kk, L;
 69 int IN[maxm][maxn];
 70 queue<int> q;
 71 void add(int u, int v, int w) {
 72     now->to = v;
 73     now->w = w;
 74     now->next = head[u];
 75     head[u] = now;
 76     now++;
 77 }
 78 void pre() {
 79     now = E;
 80     L = (1<<(2*kk));
 81     SET(head, 0);
 82     for(int i = 0; i < m; i++) {
 83         int u, v, w;
 84         scanf("%d%d%d", &u, &v,&w);
 85         add(u, v, w);
 86         add(v, u, w);
 87     }
 88     memset(s, 0, sizeof(s));
 89     for(int i = 0; i < L; i++)
 90         for(int j = 1; j <= n; j++)
 91             dp[j][i] = inf;
 92     for(int i = 1; i <= kk; i++) {
 93         s[i] = 1<<(i-1);
 94         dp[i][s[i]] = 0;
 95         s[n-i+1] = 1<<(kk+i-1);
 96         dp[n-i+1][s[n-i+1]] = 0;
 97     }
 98 
 99 }
100 bool check(int x) {
101     int ans = 0;
102     for(int i = 0; i < 2*kk; x >>= 1, i++)
103         ans += (x&1)*(i < kk ? 1 : -1);
104     return ans == 0;
105 }
106 bool go(int x, int y, int w) {
107     if(dp[x][y] > w)
108         return dp[x][y] = w, true;
109     return false;
110 }
111 void spfa() {
112     while(!q.empty()) {
113         int x = q.front()/10000;
114         int y = q.front()%10000;
115         IN[x][y] = 0;
116         q.pop();
117         for(EDGE *next = head[x]; next; next = next->next) {
118             if(go(next->to, y|s[next->to], dp[x][y] + next->w) &&  !s[next->to] && !IN[next->to][y])
119                 IN[next->to][y] = 1, q.push(next->to*10000 + y);
120         }
121     }
122 }
123 int main() {
124     
125     int T;
126     for(int t = scanf("%d" ,&T); t <= T; t++) {
127         scanf("%d%d%d", &n, &m, &kk);
128         pre();
129         memset(IN, 0, sizeof(IN));
130         for(int i = 0; i < L; i++) {
131             for(int j = 1; j <= n; j++) {
132                 for(int st = i; st; st = (st-1)&i)
133                     dp[j][i] = min(dp[j][i], dp[j][st|s[j]] + dp[j][(i-st)|s[j]]);
134                 if(dp[j][i] < inf)
135                     IN[j][i] = 1, q.push(j*10000 + i);
136             }
137             spfa();
138         }
139         for(int i = 0; i < L; i++) {
140             ans[i] = inf;
141             for(int j = 1; j <= n; j++) {
142                 ans[i] = min(ans[i], dp[j][i]);
143             }
144         }
145         for(int i = 1; i < L; i++)
146             if(check(i))
147                 for(int j = i; j ; j = (j-1)&i)
148                     if(check(j))
149                         ans[i] = min(ans[i], ans[j] + ans[i-j]);
150         if(ans[L-1] < inf)
151             cout<<ans[L-1]<<endl;
152         else cout<<"No solution"<<endl;
153     }
154     return 0;
155 }
View Code

ZOJ 3613
Wormhole Transport

题意：有n个行星上有工厂，m个行星上有资源，每个资源行星只能给一个工厂提供资源，给定行星间的连接关系，

最多能有多少个工厂能够运行，而且花费的费用最少。

与上面的题目变化在于最后DP的时候check里面改成工厂数目不少于资源行星数目就行了。

 

  1 //Template updates date: 20140316
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdio>
  5 #include <climits>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <cstring>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <stack>
 12 #include <set>
 13 #include <map>
 14 #include <cmath>
 15 #include <vector>
 16 #include <queue>
 17 #include <algorithm>
 18 #define  esp 1e-6
 19 #define  inf 0x0f0f0f0f
 20 #define  pi acos(-1.0)
 21 #define  pb push_back
 22 #define  lson l, m, rt<<1
 23 #define  rson m+1, r, rt<<1|1
 24 #define  lowbit(x) (x&(-x))
 25 #define  mp(a, b) make_pair((a), (b))
 26 #define  bit(k) (1<<(k))
 27 #define  in  freopen("solve_in.txt", "r", stdin);
 28 #define  out freopen("solve_out.txt", "w", stdout);
 29 
 30 #define  bug puts("********))))))");
 31 #define  inout in out
 32 
 33 #define  SET(a, v) memset(a, (v), sizeof(a))
 34 #define  SORT(a)   sort((a).begin(), (a).end())
 35 #define  REV(a)    reverse((a).begin(), (a).end())
 36 #define  READ(a, n) {REP(i, n) cin>>(a)[i];}
 37 #define  REP(i, n) for(int i = 0; i < (n); i++)
 38 #define  Rep(i, base, n) for(int i = base; i < n; i++)
 39 #define  REPS(s, i) for(int i = 0; s[i]; i++)
 40 #define  pf(x) ((x)*(x))
 41 #define  mod(n) ((n))
 42 #define  Log(a, b) (log((double)b)/log((double)a))
 43 #define Srand() srand((int)time(0))
 44 #define random(number) (rand()%number)
 45 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
 46 
 47 using namespace std;
 48 typedef long long  LL;
 49 typedef unsigned long long ULL;
 50 typedef vector<int> VI;
 51 typedef pair<int,int> PII;
 52 typedef vector<PII> VII;
 53 typedef vector<PII, int> VIII;
 54 typedef VI:: iterator IT;
 55 typedef map<string, int> Mps;
 56 typedef map<int, int> Mpi;
 57 typedef map<int, PII> Mpii;
 58 typedef map<PII, int> Mpiii;
 59 
 60 const int maxn = 222;
 61 const int maxm = 5555;
 62 const int LI = 1<<10;
 63 
 64 int dp[maxn][LI], d[LI], s[maxn], num[maxn], vis[maxn], inq[maxn][LI];
 65 int n, m;
 66 VI Store;
 67 queue<int> q;
 68 struct EDGE {
 69     int v, w;
 70     EDGE *nxt;
 71     EDGE() {}
 72     EDGE(int v, int w, EDGE *nxt):v(v), w(w), nxt(nxt) {}
 73 } *head[maxn], E[maxm*2], *now;
 74 void pre() {
 75     SET(head, 0);
 76     SET(dp, 0x0f);
 77     SET(d, 0x0f);
 78     SET(s, 0);
 79     SET(inq, 0);
 80     Store.clear();
 81     now = E;
 82 }
 83 void addedge(int u, int v, int w) {
 84     now->v = v;
 85     now->w = w;
 86     now->nxt = head[u];
 87     head[u] = now++;
 88 }
 89 void read() {
 90     for(int i = 1; i <= n; i++) {
 91         int u, v;
 92         scanf("%d%d", &u, &v);
 93         if(u || v)
 94             Store.pb(i);
 95         num[i] = u;
 96         vis[i] = v;
 97     }
 98     for(int i = scanf("%d", &m); i <= m; i++) {
 99         int u, v, w;
100         scanf("%d%d%d", &u, &v, &w);
101         addedge(u, v, w);
102         addedge(v, u, w);
103     }
104 }
105 bool check(int x, int &b) {
106     int a;
107     a = b = 0;
108     for(int i = 0; x; i++, x >>= 1)
109         if(x&1) {
110             a += num[Store[i]];
111             b += vis[Store[i]];
112         }
113     return a >= b;
114 }
115 bool update(int x, int y, int w) {
116     if(dp[x][y] > w)
117         return dp[x][y] = w, true;
118     return false;
119 }
120 void spfa() {
121     while(!q.empty()) {
122         int u = q.front();
123         q.pop();
124         int x = u/10000;
125         int y = u%10000;
126         inq[x][y] = 0;
127         for(EDGE *p = head[x]; p; p = p->nxt) {
128             if(update(p->v, y|s[p->v], dp[x][y] + p->w) && s[p->v] == 0 && !inq[p->v][y])
129                 inq[p->v][y] = 1, q.push(p->v*10000 + y);
130         }
131     }
132 }
133 void solve() {
134     REP(i, Store.size()) {
135         s[Store[i]] = 1<<i;
136         dp[Store[i]][s[Store[i]]] = 0;
137     }
138     int L = 1<<Store.size();
139     REP(state, L) {
140         Rep(i, 1, n+1) {
141             for(int st = state; st; st = (st-1)&state)
142                 dp[i][state] = min(dp[i][state], dp[i][st|s[i]] + dp[i][(state-st)|s[i]]);
143             if(dp[i][state] < inf)
144                 inq[i][state] = 1, q.push(i*10000 + state);
145         }
146         spfa();
147     }
148     d[0] = 0;
149     int tmp, maxans, mincost;
150     maxans = 0, mincost = 0;
151     REP(i, L) Rep(j, 1, n+1)
152     d[i] = min(d[i], dp[j][i]);
153     Rep(i, 1, L) if(check(i, tmp))
154         for(int j = i; j; j = (j-1)&i)
155             if(check(j, tmp) && check(i-j, tmp))
156                 d[i] = min(d[i], d[j] + d[i-j]);
157     REP(i, L) if(check(i, tmp) && (tmp > maxans || (tmp == maxans && d[i] < mincost)))
158         maxans = tmp, mincost = d[i];
159     printf("%d %d
", maxans, mincost);
160 }
161 int main() {
162     
163     while(scanf("%d", &n) == 1) {
164         pre();
165         read();
166         solve();
167     }
168     return 0;
169 }
View Code

不过一开始把题意看成每个资源行星可以给一个行星上所有工厂提供资源，这样一写发现还是可以写出来的，哈哈，倒是自己重新发明了一道题目。

思路是，需要枚举是哪些行星上工厂可以运行，然后算出相应工厂数目，以及这样的情况下，花费最少，由于最多4个行星上有工厂，所以这样暴力是可以的。

既然写了上一下这样的题意的代码，不能保证没有bug啊。

  1 //Template updates date: 20140316
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdio>
  5 #include <climits>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <cstring>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <stack>
 12 #include <set>
 13 #include <map>
 14 #include <cmath>
 15 #include <vector>
 16 #include <queue>
 17 #include <algorithm>
 18 #define  esp 1e-6
 19 #define  pi acos(-1.0)
 20 #define  pb push_back
 21 #define  lson l, m, rt<<1
 22 #define  rson m+1, r, rt<<1|1
 23 #define  lowbit(x) (x&(-x))
 24 #define  mp(a, b) make_pair((a), (b))
 25 #define  bit(k) (1<<(k))
 26 #define  in  freopen("solve_in.txt", "r", stdin);
 27 #define  out freopen("solve_out.txt", "w", stdout);
 28 
 29 #define  bug puts("********))))))");
 30 #define  inout in out
 31 
 32 #define  SET(a, v) memset(a, (v), sizeof(a))
 33 #define  SORT(a)   sort((a).begin(), (a).end())
 34 #define  REV(a)    reverse((a).begin(), (a).end())
 35 #define  READ(a, n) {REP(i, n) cin>>(a)[i];}
 36 #define  REP(i, n) for(int i = 0; i < (n); i++)
 37 #define  Rep(i, base, n) for(int i = base; i < n; i++)
 38 #define  REPS(s, i) for(int i = 0; s[i]; i++)
 39 #define  pf(x) ((x)*(x))
 40 #define  mod(n) ((n))
 41 #define  Log(a, b) (log((double)b)/log((double)a))
 42 #define Srand() srand((int)time(0))
 43 #define random(number) (rand()%number)
 44 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
 45 
 46 using namespace std;
 47 typedef long long  LL;
 48 typedef unsigned long long ULL;
 49 typedef vector<int> VI;
 50 typedef pair<int,int> PII;
 51 typedef vector<PII> VII;
 52 typedef vector<PII, int> VIII;
 53 typedef VI:: iterator IT;
 54 typedef map<string, int> Mps;
 55 typedef map<int, int> Mpi;
 56 typedef map<int, PII> Mpii;
 57 typedef map<PII, int> Mpiii;
 58 
 59 const int maxn = 222;
 60 const int maxm = 5555;
 61 const int LI = 1<<10;
 62 int s[maxn], inq[maxn][LI];
 63 LL dp[maxn][LI], d[LI], cost[maxn];
 64 LL inf;
 65 
 66 int n, m;
 67 LL maxans, mincost, L, temp;
 68 VI planetA, planetB;
 69 int cntA, cntB, Minx;
 70 queue<int> q;
 71 
 72 struct EDGE {
 73     int v;
 74     LL w;
 75     EDGE *nxt;
 76     EDGE() {}
 77     EDGE(int v, LL w, EDGE *nxt):v(v), w(w), nxt(nxt) {}
 78 } *head[maxn], E[maxm*2], *now;
 79 
 80 void addedge(int u, int v, int w) {
 81     now->v = v;
 82     now->w = w;
 83     now->nxt = head[u];
 84     head[u] = now++;
 85 }
 86 int maze[5][5][10]= {{}, {{},{1}},{{},{1,2},{3}},{{},{1,2,4},{3,6,5},{7}},
 87     {{},{1,2,4,8},{3,5,9,6,10,12},{7,11,13,14},{15}}
 88 };
 89 void pre() {
 90     now = E;
 91     SET(head, 0);
 92     SET(s, 0);
 93     SET(cost, 0);
 94     SET(&inf, 0x0f);
 95     maxans = 0;
 96     mincost = 0;
 97     temp = 0;
 98     planetA.clear();
 99     planetB.clear();
100     planetA.pb(-1);
101     planetB.pb(-1);
102     cntA = cntB = 0;
103 }
104 void read() {
105     Rep(i, 1, n+1) {
106         int u, v;
107         scanf("%d%d", &u, &v);
108         if(u&&v) {
109             temp += u;
110         } else {
111             if(u)
112                 planetA.pb(i), cntA++, cost[i] = u;
113             if(v)planetB.pb(i), cntB++;
114         }
115     }
116     for(int i = scanf("%d", &m); i <= m; i++) {
117         int u, v, w;
118         scanf("%d%d%d", &u, &v, &w);
119         addedge(u, v, (LL)w);
120         addedge(v, u, (LL)w);
121     }
122 }
123 LL encode(int m, int l, int j) {
124     SET(dp, 0x0f),SET(d, 0x0f);
125     LL ans = 0;
126     SET(s, 0);
127     int cnt1 = 0, cnt2 = 0;
128     for(int i = 1; i <= cntA; i++)
129         if(maze[cntA][m][l]&(1<<(i-1))) {
130             ans += cost[planetA[i]];
131             s[planetA[i]] = (1<<(cnt1++));
132             dp[planetA[i]][s[planetA[i]]] = 0;
133         }
134     for(int i = 1; i <= cntB; i++)
135         if(maze[cntB][m][j]&(1<<(i-1))) {
136             s[planetB[i]] = (1<<(cnt2++));
137             if(s[planetB[i]] < (1<<(m)))
138                 s[planetB[i]] += ((1<<m)-1);
139             dp[planetB[i]][s[planetB[i]]] = 0;
140         }
141     return ans;
142 }
143 bool update(int x, int y, LL w) {
144     if(dp[x][y] > w)
145         return dp[x][y] = w, true;
146     return false;
147 }
148 void spfa() {
149     while(!q.empty()) {
150         int u = q.front();
151         q.pop();
152         int x = u/20000;
153         int y = u%20000;
154         inq[x][y] = 0;
155         for(EDGE *p = head[x]; p; p = p->nxt) {
156             if(update(p->v, y|s[p->v], dp[x][y]+p->w) && (y|s[p->v] == y) && !inq[p->v][y])
157                 inq[p->v][y] = 1, q.push(p->v*20000 + y);
158         }
159     }
160 }
161 bool check(int x) {
162     int ans = 0;
163     for(int i = 0; x; x >>= 1, i++)
164         ans += (i < Minx ? 1 : -1)*(x&1);
165     return ans == 0;
166 }
167 void solve() {
168     Minx = min(cntA,cntB);
169     while(Minx) {
170         L = (1<<(2*Minx));
171         for(int i = 0; maze[cntA][Minx][i]; i++)
172             for(int j = 0; maze[cntB][Minx][j]; j++) {
173                 LL tmp = encode(Minx, i, j);
174                 SET(inq, 0);
175                 for(int state = 0; state < L; state++) {
176                     for(int x = 1; x <= n; x++) {
177                         for(int st = state; st; st = (st-1)&state)
178                             dp[x][state] = min(dp[x][state], dp[x][st|s[x]] + dp[x][s[x]|(state-st)]);
179                         if(dp[x][state] < inf)
180                             inq[x][state] = 1, q.push(x*20000 + state);
181                     }
182                     spfa();
183                 }
184                 for(int i = 0; i < L; i++)
185                     for(int j = 1; j <= n; j++)
186                         d[i] = min(d[i], dp[j][i]);
187                 d[0] = 0;
188                 for(int i = 1; i < L; i++)
189                     if(check(i))
190                         for(int j = i; j; j = (j-1)&i)
191                             if(check(j))
192                                 d[i] = min(d[i], d[j] + d[i-j]);
193 
194                 if(d[L-1] < inf && (tmp > maxans || (tmp == maxans && d[L-1] < mincost)))
195                     maxans = tmp, mincost = d[L-1];
196             }
197         Minx--;
198     }
199     maxans += temp;
200     printf("%lld %lld
", maxans, mincost);
201 }
202 int main() {
203     
204     while(scanf("%d", &n) != EOF) {
205         pre();
206         read();
207         solve();
208     }
209     return 0;
210 }
View Code

HYSBZ 2595
        游览计划

给定n*m矩阵，一些格子为景点，要求选择一些格子使得景点之间两两连通，非景点的格子上必须安排相应数目志愿者。

这个题目只不过变成了点带权值，所以进行第一种状态转移时，应该注意减去重复计算的权值，然后最后发现记录路径的时候不会，

看了别人代码发现还是太年轻，直接把中间过渡状态记录最后一步步回溯，记录相应格子就是了。

  1 //Template updates date: 20140316
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdio>
  5 #include <climits>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <cstring>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <stack>
 12 #include <set>
 13 #include <map>
 14 #include <cmath>
 15 #include <vector>
 16 #include <queue>
 17 #include <algorithm>
 18 #define  esp 1e-6
 19 #define  inf 0x0f0f0f0f
 20 #define  pi acos(-1.0)
 21 #define  pb push_back
 22 #define  lson l, m, rt<<1
 23 #define  rson m+1, r, rt<<1|1
 24 #define  lowbit(x) (x&(-x))
 25 #define  mp(a, b) make_pair((a), (b))
 26 #define  bit(k) (1<<(k))
 27 #define  in  freopen("solve_in.txt", "r", stdin);
 28 #define  out freopen("solve_out.txt", "w", stdout);
 29 
 30 #define  bug puts("********))))))");
 31 #define  inout in out
 32 
 33 #define  SET(a, v) memset(a, (v), sizeof(a))
 34 #define  SORT(a)   sort((a).begin(), (a).end())
 35 #define  REV(a)    reverse((a).begin(), (a).end())
 36 #define  READ(a, n) {REP(i, n) cin>>(a)[i];}
 37 #define  REP(i, n) for(int i = 0; i < (n); i++)
 38 #define  Rep(i, base, n) for(int i = base; i < n; i++)
 39 #define  REPS(s, i) for(int i = 0; s[i]; i++)
 40 #define  pf(x) ((x)*(x))
 41 #define  mod(n) ((n))
 42 #define  Log(a, b) (log((double)b)/log((double)a))
 43 #define Srand() srand((int)time(0))
 44 #define random(number) (rand()%number)
 45 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
 46 
 47 using namespace std;
 48 typedef long long  LL;
 49 typedef unsigned long long ULL;
 50 typedef vector<int> VI;
 51 typedef pair<int,int> PII;
 52 typedef vector<PII> VII;
 53 typedef vector<PII, int> VIII;
 54 typedef VI:: iterator IT;
 55 typedef map<string, int> Mps;
 56 typedef map<int, int> Mpi;
 57 typedef map<int, PII> Mpii;
 58 typedef map<PII, int> Mpiii;
 59 
 60 const int maxn = 11;
 61 const int LI = 1<<11;
 62 
 63 int maze[maxn][maxn], dp[maxn*maxn][LI], inq[maxn*maxn][LI], s[maxn*maxn], vis[maxn][maxn];
 64 int n, m, L ,id;
 65 int pre[maxn*maxn][LI];
 66 char ans[maxn][maxn];
 67 int dx[] = {-1, 0, 1, 0};
 68 int dy[] = {0, 1, 0, -1};
 69 queue<int> q;
 70 VI po;
 71 
 72 bool check(int x,int y) {
 73     return x >= 0 && x < n && y >= 0 && y < m;
 74 }
 75 bool update(int x, int y, int w) {
 76     if(dp[x][y] > w) return dp[x][y] = w, true;
 77     return false;
 78 }
 79 void ID(int x, int y) {
 80     s[x*m+y] = 1<<id;
 81     dp[x*m+y][s[x*m+y]] = 0;
 82     po.pb(x*m+y);
 83     id++;
 84 }
 85 void preprocess() {
 86     po.clear();
 87     SET(inq, 0);
 88     SET(vis, 0);
 89     SET(s, 0);
 90     SET(pre, -1);
 91     SET(dp, 0x0f);
 92     id = 0;
 93 }
 94 void spfa() {
 95 
 96     while(!q.empty()) {
 97         int u = q.front();
 98         q.pop();
 99         int x = u/2000;
100         int y = u%2000;
101         inq[x][y] = 0;
102         int xx = x/m;
103         int yy = x%m;
104 
105         REP(k, 4) {
106             int nx = xx + dx[k];
107             int ny = yy + dy[k];
108             if(!check(nx, ny))
109                 continue;
110             int v = nx*m + ny;
111             if(update(v, y|s[v], dp[x][y] + maze[nx][ny]) ) {
112                 pre[v][y|s[v]] = u;
113                 if(!s[v] && !inq[v][y])
114                     inq[v][y] = 1, q.push(v*2000 + y);
115             }
116         }
117     }
118 }
119 void solve() {
120     L = 1<<id;
121     REP(state, L) {
122         REP(i, n) REP(j, m) {
123             int u = i*m+j;
124             for(int st = state; st; st = (st-1)&state){
125                 if(s[u] && !(s[u] & state))
126                     continue;
127                 if(dp[u][state] > dp[u][st|s[u]] + dp[u][s[u]|(state-st)]-maze[i][j]) {
128                     dp[u][state] = dp[u][st|s[u]] + dp[u][s[u]|(state-st)] - maze[i][j];
129                     pre[u][state] = u*2000 + (st|s[u]);
130                 }
131             }
132             if(dp[u][state] < inf)
133                 inq[u][state] = 1, q.push(u*2000 + state);
134         }
135         spfa();
136     }
137 }
138 void BackTrace(int x, int y) {
139     int xx = x/m;
140     int yy = x%m;
141     vis[xx][yy] = 1;
142     int u = pre[x][y], nx, ny;
143     if(u == -1)
144         return;
145     nx = u/2000;
146     ny = u%2000;
147     BackTrace(nx, ny);
148     if(nx == x)
149         BackTrace(nx, (y-ny)|s[x]);
150 }
151 void output() {
152     if(id == 0 || dp[po[0]][L-1] == 0) {
153         cout<<0<<endl;
154         REP(i, n) {
155             REP(j, m)
156             putchar(ans[i][j]);
157             puts("");
158         }
159     } else {
160         int tmp1 = dp[po[0]][L-1];
161         cout<<tmp1<<endl;
162         BackTrace(po[0], L-1);
163         REP(i, n) {
164             REP(j, m) {
165                 if(!maze[i][j])
166                     putchar('x');
167                 else if(vis[i][j])
168                     putchar('o');
169                 else putchar('_');
170             }
171             puts("");
172         }
173     }
174 }
175 int main() {
176 
177     scanf("%d%d", &n, &m);{
178         preprocess();
179         REP(i, n) REP(j, m) {
180             scanf("%d", &maze[i][j]);
181             if(!maze[i][j])
182                 ID(i, j), ans[i][j] = 'x';
183             else ans[i][j] = '_';
184         }
185         solve();
186         output();
187     }
188     return 0;
189 }
View Code

HDU - 3311

Dig The Wells
给定n个和尚居住地方和其他m个地方，n+m个地方都可以挖井，花费cost[i]，以及这n+m个地方中各种连接路径及花费，选择相应的路径，及在某些地方挖井，所有的和尚都能有水井 到达。
分析：每个连通图分量里面最多只有一口水井。
法一：可以先当做普通斯坦纳树处理dp[i][s]表示，i为根，s为连通状况的最少花费，然后dp的时候加上在i点挖井的花费。
代码：
  1 //Template updates date: 20140316
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdio>
  5 #include <climits>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <cstring>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <stack>
 12 #include <set>
 13 #include <map>
 14 #include <cmath>
 15 #include <vector>
 16 #include <queue>
 17 #include <algorithm>
 18 #define  esp 1e-6
 19 #define  inf 0x3f3f3f3f
 20 #define  pi acos(-1.0)
 21 #define  pb push_back
 22 #define  lson l, m, rt<<1
 23 #define  rson m+1, r, rt<<1|1
 24 #define  lowbit(x) (x&(-x))
 25 #define  mp(a, b) make_pair((a), (b))
 26 #define  bit(k) (1<<(k))
 27 #define  in  freopen("solve_in.txt", "r", stdin);
 28 #define  out freopen("solve_out.txt", "w", stdout);
 29 
 30 #define  bug puts("********))))))");
 31 #define  inout in out
 32 
 33 #define  SET(a, v) memset(a, (v), sizeof(a))
 34 #define  SORT(a)   sort((a).begin(), (a).end())
 35 #define  REV(a)    reverse((a).begin(), (a).end())
 36 #define  READ(a, n) {REP(i, n) cin>>(a)[i];}
 37 #define  REP(i, n) for(int i = 0; i < (n); i++)
 38 #define  Rep(i, base, n) for(int i = base; i < n; i++)
 39 #define  REPS(s, i) for(int i = 0; s[i]; i++)
 40 #define  pf(x) ((x)*(x))
 41 #define  mod(n) ((n))
 42 #define  Log(a, b) (log((double)b)/log((double)a))
 43 #define Srand() srand((int)time(0))
 44 #define random(number) (rand()%number)
 45 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
 46 
 47 using namespace std;
 48 typedef long long  LL;
 49 typedef unsigned long long ULL;
 50 typedef vector<int> VI;
 51 typedef pair<int,int> PII;
 52 typedef vector<PII> VII;
 53 typedef vector<PII, int> VIII;
 54 typedef VI:: iterator IT;
 55 typedef map<string, int> Mps;
 56 typedef map<int, int> Mpi;
 57 typedef map<int, PII> Mpii;
 58 typedef map<PII, int> Mpiii;
 59 
 60 const int maxn = 1100;
 61 const int maxm = 5000*2 + 1000;
 62 const int LI = (1<<10);
 63 
 64 int dp[maxn][LI], d[LI], inq[maxn][LI], s[maxn], cost[maxn];
 65 int n, m, p;
 66 int L;
 67 queue<int> q;
 68 
 69 struct EDGE {
 70     int v, w;
 71     EDGE *nxt;
 72     EDGE() {}
 73     EDGE(int v, int w, EDGE *nxt):v(v),w(w), nxt(nxt) {}
 74 } *head[maxn], E[maxm], *cur;
 75 
 76 void addedge(int u, int v, int w) {
 77     cur->v = v;
 78     cur->w = w;
 79     cur->nxt = head[u];
 80     head[u] = cur++;
 81 
 82 }
 83 void preprocess() {
 84     SET(head, 0);
 85     cur = E;
 86     SET(s, 0);
 87     SET(inq, 0);
 88     SET(dp, 0x3f);
 89     SET(d, 0x3f);
 90     L = 1<<n;
 91 }
 92 bool update(int x, int y, int w) {
 93     if(dp[x][y] > w) return dp[x][y] = w, true;
 94     return false;
 95 }
 96 void spfa() {
 97     while(!q.empty()) {
 98         int u = q.front();
 99         q.pop();
100         int x = u/10000;
101         int y = u%10000;
102         inq[x][y] = 0;
103         for(EDGE *p = head[x]; p; p = p->nxt) {
104             if(update(p->v, y|s[p->v], dp[x][y] + p->w) && (y|s[p->v]) == y && !inq[p->v][y])
105                 inq[p->v][y] = 1, q.push(p->v*10000 + y);
106         }
107     }
108 }
109 void solve() {
110     REP(i, n+m) scanf("%d", &cost[1+i]);
111     REP(i, n)
112     s[i+1] = 1<<i, dp[1+i][s[i+1]] = 0;
113     REP(i, p) {
114         int u, v, w;
115         scanf("%d%d%d", &u, &v, &w);
116         addedge(u, v, w);
117         addedge(v, u, w);
118     }
119     Rep(state,1, L) {
120         Rep(i, 1, n+m+1) {
121 //            if(s[i] && !(s[i] & state))
122 //                continue;
123             for(int st = state&(state-1); st; st = (st-1)&state) {
124                 dp[i][state] = min(dp[i][state], dp[i][st|s[i]] + dp[i][(state-st)|s[i]]);
125             }
126             if(dp[i][state] < inf)
127                 inq[i][state] = 1, q.push(i*10000 + state);
128         }
129         spfa();
130     }
131     Rep(i, 1, L)
132     Rep(j, 1, n+m+1)
133     d[i] = min(d[i], dp[j][i] + cost[j]);
134     Rep(st, 1, L)
135     for(int ss = (st-1)&st; ss; ss = (ss-1)&st)
136         d[st] = min(d[st], d[ss] + d[st-ss]);
137     printf("%d
", d[L-1]);
138 }
139 
140 int main() {
141 
142     while(scanf("%d%d%d", &n, &m, &p) == 3) {
143         preprocess();
144         solve();
145     }
146     return 0;
147 }
View Code

法二：用dp[i][s]表示以i为根且在i点挖井，连通状态为s的最小花费，不过转移时应该注意重复计算的cost[i]，两种情况下的转移都要自习考虑

代码：

  1 //Template updates date: 20140316
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdio>
  5 #include <climits>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <cstring>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <stack>
 12 #include <set>
 13 #include <map>
 14 #include <cmath>
 15 #include <vector>
 16 #include <queue>
 17 #include <algorithm>
 18 #define  esp 1e-6
 19 #define  inf 0x0f0f0f0f
 20 #define  pi acos(-1.0)
 21 #define  pb push_back
 22 #define  lson l, m, rt<<1
 23 #define  rson m+1, r, rt<<1|1
 24 #define  lowbit(x) (x&(-x))
 25 #define  mp(a, b) make_pair((a), (b))
 26 #define  bit(k) (1<<(k))
 27 #define  in  freopen("solve_in.txt", "r", stdin);
 28 #define  out freopen("solve_out.txt", "w", stdout);
 29 
 30 #define  bug puts("********))))))");
 31 #define  inout in out
 32 
 33 #define  SET(a, v) memset(a, (v), sizeof(a))
 34 #define  SORT(a)   sort((a).begin(), (a).end())
 35 #define  REV(a)    reverse((a).begin(), (a).end())
 36 #define  READ(a, n) {REP(i, n) cin>>(a)[i];}
 37 #define  REP(i, n) for(int i = 0; i < (n); i++)
 38 #define  Rep(i, base, n) for(int i = base; i < n; i++)
 39 #define  REPS(s, i) for(int i = 0; s[i]; i++)
 40 #define  pf(x) ((x)*(x))
 41 #define  mod(n) ((n))
 42 #define  Log(a, b) (log((double)b)/log((double)a))
 43 #define Srand() srand((int)time(0))
 44 #define random(number) (rand()%number)
 45 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)
 46 
 47 using namespace std;
 48 typedef long long  LL;
 49 typedef unsigned long long ULL;
 50 typedef vector<int> VI;
 51 typedef pair<int,int> PII;
 52 typedef vector<PII> VII;
 53 typedef vector<PII, int> VIII;
 54 typedef VI:: iterator IT;
 55 typedef map<string, int> Mps;
 56 typedef map<int, int> Mpi;
 57 typedef map<int, PII> Mpii;
 58 typedef map<PII, int> Mpiii;
 59 const int maxn = 1100;
 60 const int maxm = 5000*2 + 1000;
 61 const int LI = (1<<10);
 62 
 63 int dp[maxn][LI], d[LI], inq[maxn][LI], s[maxn], cost[maxn];
 64 int n, m, p;
 65 int L;
 66 queue<int> q;
 67 
 68 struct EDGE {
 69     int v, w;
 70     EDGE *nxt;
 71     EDGE() {}
 72     EDGE(int v, int w, EDGE *nxt):v(v),w(w), nxt(nxt) {}
 73 } *head[maxn], E[maxm], *cur;
 74 
 75 void addedge(int u, int v, int w) {
 76     u--, v--;
 77     cur->v = v;
 78     cur->w = w;
 79     cur->nxt = head[u];
 80     head[u] = cur++;
 81 
 82 }
 83 void preprocess() {
 84     SET(head, 0);
 85     cur = E;
 86     SET(s, 0);
 87     SET(inq, 0);
 88     SET(dp, 0x0f);
 89     SET(d, 0x0f);
 90     L = 1<<n;
 91 }
 92 bool update(int x, int y, int w) {
 93     if(dp[x][y] >= w) return dp[x][y] = w, true;
 94     return false;
 95 }
 96 void spfa() {
 97     while(!q.empty()) {
 98         int u = q.front();
 99         q.pop();
100         int x = u/1000;
101         int y = u%1000;
102         inq[x][y] = 0;
103         for(EDGE *p = head[x]; p; p = p->nxt) {
104             if(update(p->v, y|s[p->v], dp[x][y] + p->w + cost[p->v]-cost[x]) && !s[p->v] && !inq[p->v][y])
105                 inq[p->v][y] = 1, q.push(p->v*1000 + y);
106         }
107     }
108 }
109 void solve() {
110     REP(i, n+m) scanf("%d", &cost[i]);
111     REP(i, n)
112     s[i] = 1<<i, dp[i][s[i]] = cost[i];
113     REP(i, p) {
114         int u, v, w;
115         scanf("%d%d%d", &u, &v, &w);
116         addedge(u, v, w);
117         addedge(v, u, w);
118     }
119     REP(state, L) {
120         REP(i, n+m) {
121             if(s[i] && !(s[i] & state))
122                 continue;
123             for(int st = state; st; st = (st-1)&state) {
124                 dp[i][state] = min(dp[i][state], dp[i][st|s[i]] + dp[i][(state-st)|s[i]] - cost[i]);
125             }
126             if(dp[i][state] < inf)
127                 inq[i][state] = 1, q.push(i*1000 + state);
128         }
129         spfa();
130     }
131     d[0] = 0;
132     REP(i, L)
133     REP(j, n+m)
134     d[i] = min(d[i], dp[j][i]);
135     Rep(st, 1, L)
136     for(int ss = (st-1)&st; ss; ss = (ss-1)&st)
137         d[st] = min(d[st], d[ss] + d[st-ss]);
138     cout<<d[L-1]<<endl;
139 }
140 
141 int main() {
142     
143     while(scanf("%d%d%d", &n, &m, &p) == 3) {
144         preprocess();
145         solve();
146     }
147     return 0;
148 }
View Code

看了别人发现其实还有一种方法就是虚拟一个点，然后连一条cost[i]的边到n+m个点，最后对0,1,2...n这n+1个点求斯坦纳树，可是好像怎么写都不对，

先挖坑。。。

 

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/rootial/p/3847717.html