Steiner Tree:

Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals,

the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices).

也就是对于给定的点集求一颗包含他的最小生成树(可以包含额外的点)

$ST$是$NPC$问题，规模小的情况可以使用状压$DP$解决

$f[i][s]$表示根在$i$，连通的点集为$s$的(仅包括给定点集中的点)的最小花费

有两种转移：

对于点权的情况（边权类似）：

$f[i][s]=min{f[i][s']+f[i][s-s']-val[i]}$，划分成两个子集，具有阶段性普通$DP$就可以

$f[i][s]=min{f[i'][s]+val[i]}$，从一颗树扩展而来，阶段性不明显，但满足三角不等式，使用$spfa$求解

那么过程就很清楚了

从小到大枚举集合和点
第一种转移枚举子集
第二种转移对当前集合使用spfa

然后就到黄学长哪里仿写了份模板

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

#define pii pair<int,int>

#define MP make_pair

#define fir first

#define sec second

typedef long long ll;

const int N=,S=(<<)+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,k,a[N][N];

int f[N][N][S];

struct Path{

    int i,j,s;

    Path(){}

    Path(int a,int b,int c):i(a),j(b),s(c){}

}pre[N][N][S];

queue<pii> q;

bool inq[N][N];

int dx[]={,-,,},dy[]={,,,-};

void spfa(int s){

    while(!q.empty()){

        int x=q.front().fir,y=q.front().sec;

        inq[x][y]=;q.pop();

        for(int k=;k<;k++){

            int i=x+dx[k],j=y+dy[k];

            if(i<||i>n||j<||j>m) continue;

            if(f[i][j][s]>f[x][y][s]+a[i][j]){

                f[i][j][s]=f[x][y][s]+a[i][j];

                pre[i][j][s]=Path(x,y,s);

                if(!inq[i][j])

                    q.push(MP(i,j)),inq[i][j]=;

            }

        }

    }

}

bool vis[N][N];

void dfs(int x,int y,int s){

    vis[x][y]=;

    Path t=pre[x][y][s];

    if(t.i==&&t.j==) return;

    dfs(t.i , t.j , t.s);

    if(t.i==x && t.j==y) dfs(t.i , t.j , s-t.s);

}

int main(){

    freopen("in","r",stdin);

    n=read();m=read();

    memset(f,0x3f,sizeof(f));

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++){

            a[i][j]=read();

            if(!a[i][j]) f[i][j][<<k]=,k++;

        }

    int All=<<k;

    for(int sa=;sa<All;sa++){

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++){

                for(int s=sa&(sa-);s;s=sa&(s-)){

                    int _=f[i][j][s]+f[i][j][sa-s]-a[i][j];

                    if(_<f[i][j][sa]){

                        f[i][j][sa]=_;

                        pre[i][j][sa]=Path(i,j,s);

                    }

                }

                if(f[i][j][sa]<INF) q.push(MP(i,j)),inq[i][j]=;

            }

        spfa(sa);

    }

    int x=,y=,flag=;

    for(int i=;i<=n&&!flag;i++)

        for(int j=;j<=m;j++) if(!a[i][j]) {x=i;y=j;flag=;break;}

    dfs(x,y,All-);

    printf("%d\n",f[x][y][All-]);

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(a[i][j]==) putchar('x');

            else if(vis[i][j]) putchar('o');

            else putchar('_');

        }

        puts("");

    }

}

巴特西

BZOJ 2595: [Wc2008]游览计划 [DP 状压斯坦纳树 spfa]【学习笔记】

Steiner Tree:

最新文章

热门文章

巴特西

BZOJ 2595: [Wc2008]游览计划 [DP 状压 斯坦纳树 spfa]【学习笔记】

Steiner Tree:

最新文章

热门文章

BZOJ 2595: [Wc2008]游览计划 [DP 状压斯坦纳树 spfa]【学习笔记】