欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

最小斯坦纳树初探

程序员文章站 2022-05-14 09:41:37
问题描述 斯坦纳树问题是组合优化学科中的一个问题。将指定点集合中的所有点连通,且边权总和最小的生成树称为最小斯坦纳树(Minimal Steiner Tree),其实最小生成树是最小斯坦纳树的一种特殊情况。而斯坦纳树可以理解为使得指定集合中的点连通的树,但不一定最小。(by "Angel_Kitty ......

问题描述

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

解决方案

似乎没有多项式算法。在数据范围允许时可使用dp来解。具体地,设\(f[i,s]\)为根在点\(i\),树中包含的指定集合点的集合为\(s​\)时的最优解。两种转移
\[ f[i,s]=\min_{t\subset 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_{t\subset 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_{t\subset s} f[i,j,t]+f[i',j's-t]=\min_{t\subset 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("%d\n",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_{k\in s}ki[k]]\\ dp[s]=\min_{t\subset 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("%d\n",dp[(1<<p)-1]);
    return 0;
} 

bzoj4774 修路

hdu4085 peach blossom spring

zoj3613 wormhole transport