c/c++语言开发共享最小斯坦纳树初探

问题描述

斯坦纳树问题是组合优化学科中的一个问题。将指定点集合中的所有点连通，且边权总和最小的生成树称为最小斯坦纳树（minimal steiner tree），其实最小生成树是最小斯坦纳树的一种特殊情况。而斯坦纳树可以理解为使得指定集合中的点连通的树，但不一定最小。（by angel_kitty）

解决方案

似乎没有多项式算法。在数据范围允许时可使用dp来解。具体地，设(f[i,s])为根在点(i)，树中包含的指定集合点的集合为(s​)时的最优解。两种转移
[ f[i,s]=min_{tsubset s} f[i,t]+f[i',s-t]+e[i',i]\ f[i,s]=min f[i',s]+e[i',i] ]

显然第二种转移需要迭代/最短路算法。由于存在第二种转移，假设转移时能保证(f[*,t]​)已经被处理好，第一种转移转移可以进一步简化为
[ f[i,s]=min_{tsubset s} f[i,t]+f[i,s-t] ]
这样做就大功告成了。

练习题

bzoj2595 [wc2008]游览计划

最小化点权和，大致相同，设(f[i,j,s])为根在点((i,j))，指定集合状态为(s)的最小点权和，转移有
[ f[i,j,s]=min f[i',j',s]+c[i,j]\ f[i,j,s]=min_{tsubset s} f[i,j,t]+f[i',j's-t]=min_{tsubset s} f[i,j,t]+f[i,j,s-t]-c[i,j] ]

#include <bits/stdc++.h> using namespace std;  const int n=11; const int inf=0x3f3f3f3f; const int dx[]={0,0,-1,1}; const int dy[]={-1,1,0,0};  int n,m,k,st[n][n]; int vis[n][n],a[n][n],f[n][n][1<<n],pre[n][n][1<<n]; std::queue<int> q; bool inq[n*n];  int ecd(int i,int j) {return i*10+j;} int ecd(int i,int j,int s) {return i*100000+j*10000+s;} void dcd(int c,int&i,int&j) {i=c/10,j=c%10;} void dcd(int c,int&i,int&j,int&s) {i=c/100000,j=(c/10000)%10,s=c%10000;}  bool upd(int i,int j,int s,int p,int q,int t,int w) {     if(f[i][j][s]>w) {         f[i][j][s]=w;         pre[i][j][s]=ecd(p,q,t);         return 1;     }     return 0; } void spfa(int s) {     int x,y,i,j,tmp;     while(!q.empty()) {         int x=q.front();         q.pop();         inq[x]=0;         dcd(x,i,j);         for(int k=0; k<4; ++k) {             x=i+dx[k],y=j+dy[k];             if(x<0||x>=n||y<0||y>=m) continue;             if(upd(x,y,s,i,j,s,f[i][j][s]+a[x][y])&&!inq[tmp=ecd(x,y)]) {                 q.push(tmp),inq[tmp]=1;             }         }     } } void dfs(int i,int j,int s) {     int p,q,t;     vis[i][j]=1;     if(!pre[i][j][s]) return;     dcd(pre[i][j][s],p,q,t);     dfs(p,q,t);     if(p==i&&q==j) dfs(p,q,s^t); }  int main() {     memset(f,inf,sizeof f);     scanf("%d%d",&n,&m);     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 fll=1<<k,tmp;     for(int s=1; s<fll; ++s) {         for(int i=0; i<n; ++i)          for(int j=0; j<m; ++j) {             for(int t=s&(s-1); t; t=(t-1)&s)                  upd(i,j,s, i,j,t, f[i][j][t]+f[i][j][s^t]-a[i][j]);             if(f[i][j][s]!=inf) {                 q.push(tmp=ecd(i,j));                 inq[tmp]=1;             }         }         spfa(s);     }     for(int i=0; i<n; ++i)      for(int j=0; j<m; ++j) if(!a[i][j]) {         printf("%dn",f[i][j][fll-1]);         dfs(i,j,fll-1);         for(int p=0; p<n; ++p,puts(""))          for(int q=0; q<m; ++q) {             if(!a[p][q]) putchar('x');             else if(vis[p][q]) putchar('o');             else putchar('_');         }         return 0;     }  }

bzoj4006 [jloi2015]管道连接

需要处理出同种频道的最小斯坦纳树，在进行dp组合得到最优解。设(f[i,s])为根在(i)包含关键点集为(s)的最小边权和，(dp[s])表示包含频道集为(s)的最小边权和，(ki[i])表示频道(i)包含的关键点集，转移有
[ dp[s]=min_{i=1}^n f[i,cup_{kin s}ki[k]]\ dp[s]=min_{tsubset s} dp[t]+dp[s-t] ]

#include <bits/stdc++.h> using namespace std; const int n=1003; const int inf=0x3f3f3f3f;  int n,m,p; int head[n],to[n<<3],len[n<<3],last[n<<3]; int ki[n],f[n][1<<10],dp[1<<10];  void add_edge(int x,int y,int w) {     static int cnt=1;     to[cnt]=y;     len[cnt]=w;     last[cnt]=head[x];     head[x]=cnt++; } queue<int> q; bool inq[n]; void spfa(int s) {     for(int i=1; i<=n; ++i) {         inq[i]=1; q.push(i);     }     while(!q.empty()) {         int x=q.front(); q.pop();         inq[x]=0;         for(int i=head[x]; i; i=last[i]) {             if(f[to[i]][s]>f[x][s]+len[i]) {                 f[to[i]][s]=f[x][s]+len[i];                 if(!inq[to[i]]) {                     inq[to[i]]=1;                     q.push(to[i]);                 }             }         }     } }   int main() {     scanf("%d%d%d",&n,&m,&p);     for(int i=1,x,y,w; i<=m; ++i) {         scanf("%d%d%d",&x,&y,&w);         add_edge(x,y,w);         add_edge(y,x,w);      }      memset(f,inf,sizeof f);     for(int i=1,x,y; i<=p; ++i) {         scanf("%d%d",&x,&y);         ki[x]|=1<<(i-1);         f[y][1<<(i-1)]=0;     }     for(int s=1; s<(1<<p); ++s) {         for(int i=1; i<=n; ++i)          for(int t=s&(s-1); t; t=(t-1)&s) {             f[i][s]=min(f[i][s],f[i][t]+f[i][s^t]);         }         spfa(s);     }     memset(dp,inf,sizeof dp);     dp[0]=0;     for(int s=1; s<(1<<p); ++s) {         int k=0;         for(int i=0; i<p; ++i) if((s>>i)&1) k|=ki[i+1];         for(int i=0; i<n; ++i) dp[s]=min(dp[s],f[i][k]);         for(int t=s&(s-1); t; t=(t-1)&s) dp[s]=min(dp[s]s,dp[t]+dp[s^t]);     }     printf("%dn",dp[(1<<p)-1]);     return 0; } 

bzoj4774 修路

hdu4085 peach blossom spring

zoj3613 wormhole transport