话说挺早就写过斯坦纳树了，不过当时没怎么总结，也不是很理解……现在来个小结吧~
斯坦纳树就是包含给定点的最小生成树(个人理解权值应当为正)。
一般来讲，给定点的数目应该很小吧。。。于是我们可以用状压DP来解决。
需要2个方程：
f[st][i]表示连通性至少为st，且经过i点的最小距离
方程1.f[st][i] = Min{f[s][i] + f[st - s][i]}(s为st的子集)
方程2.f[st][i] = Min{f[st][j] + w(i,j)}(i,j之间有边相连)
这里大家可能会有疑问，为什么是两个方程？
因为单凭第一个方程转移是不够准确的，会出现重点的问题。不过也一定包含合法的转移，所以我们要通过第二个方程来转移。如果我没有理解错，这也就是为什么这种方法不能应用于有负权的图上。
第一个直接枚举子集，完了以后用SPFA转移下一个（当然也可以用floyed）。
void SPFA(int sta) { while (!q.empty()) { int i,j; unpack(q.front(),i,j); inq[q.front()] = 0;q.pop(); for (int k = 0; k < 4; ++k) { int x = d[k][0] + i,y = d[k][1] + j,tmp; if (x == -1 || y == -1 || x == n || y == m) continue; if (update(x,y,sta,i,j,sta,f[i][j][sta] + a[x][y]) && !inq[tmp = pack(x,y)]) q.push(tmp),inq[tmp] = 1; } } }要记住f[st][i]表示连通性至少为st，是至少。
for (int sta = 1,tmp; sta < Max_s; ++sta) { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { for (int s = sta&(sta - 1); s; s = (s - 1)&sta) update(i,j,sta,i,j,s,f[i][j][s] + f[i][j][sta - s] - a[i][j]); if (f[i][j][sta] != INF) q.push(tmp = pack(i,j)),inq[tmp] = 1; } SPFA(sta); }
这样转移就可以了。
/************************************************************** Problem: 2595 User: lazycal Language: C++ Result: Accepted Time:144 ms Memory:1640 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <queue> using std::queue; queue<int>q; const int N = 10,INF = 0xf0f0f0f; const int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int f[N][N][1<<N],n,m,a[N][N],st[N][N],K,pre[N][N][1<<N]; bool vis[N][N],inq[N*N]; int pack(const int x,const int y){return x*10 + y;} int pack2(const int x,const int y,const int s){return x*100000 + y*10000 + s;} void unpack(const int x,int &i,int &j){i = x/10; j = x;} void unpack2(const int x,int &i,int &j,int &s){s = x000; j = (x/10000); i = x/100000;} bool update(const int x,const int y,const int news,const int i,const int j,const int sta,const int w) { if (f[x][y][news] > w) return f[x][y][news] = w,pre[x][y][news] = pack2(i,j,sta),true; return false; } void SPFA(int sta) { while (!q.empty()) { int i,j; unpack(q.front(),i,j); inq[q.front()] = 0;q.pop(); for (int k = 0; k < 4; ++k) { int x = d[k][0] + i,y = d[k][1] + j,tmp; if (x == -1 || y == -1 || x == n || y == m) continue; if (update(x,y,sta/*|st[x][y]*/,i,j,sta,f[i][j][sta] + a[x][y]) /*&& (sta|st[x][y]) == sta*/ && !inq[tmp = pack(x,y)]) q.push(tmp),inq[tmp] = 1; } } } void dfs(const int i,const int j,const int s) { if (!pre[i][j][s]) return; int x,y,ns; vis[i][j] = 1; unpack2(pre[i][j][s],x,y,ns); dfs(x,y,ns); if (x == i && y == j) dfs(x,y,s - ns); } void output() { for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) if (!a[i][j]) printf("x"); else if (vis[i][j]) printf("o"); else printf("_"); puts(""); } } int main() { #ifndef ONLINE_JUDGE freopen("2595.in","r",stdin); freopen("2595.out","w",stdout); #endif scanf("%d%d",&n,&m); memset(f,0xf,sizeof f); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { scanf("%d",&a[i][j]); if (!a[i][j]) st[i][j] = 1<<(K++),f[i][j][st[i][j]] = 0; } int Max_s = (1 << K); for (int sta = 1,tmp; sta < Max_s; ++sta) { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { //if (a[i][j] && !(st[i][j]&sta)) continue; for (int s = sta&(sta - 1); s; s = (s - 1)&sta) update(i,j,sta,i,j,s,f[i][j][s] + f[i][j][sta - s] - a[i][j]); if (f[i][j][sta] != INF) q.push(tmp = pack(i,j)),inq[tmp] = 1;//test!!!!!!!!!!!!!!!!!!!!!!!!!!!!! } SPFA(sta); // printf("\n%d\n",sta); // for (int i = 0; i < n; ++i) { // for (int j = 0; j < m; ++j) printf("%d ",f[i][j][sta]); // puts(""); // } } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (!a[i][j]) { printf("%d\n",f[i][j][Max_s - 1]); dfs(i,j,Max_s - 1); output(); return 0; } }
转载于:https://www.cnblogs.com/lazycal/p/bzoj-2595.html
相关资源：JAVA上百实例源码以及开源项目