P4294 [WC2008]游览计划(斯坦纳树)

最小斯坦纳树用于处理联通集合中指定的点的最小代价，一般来说可以通过其他不属于集合的点

最小生成树是特殊的斯坦纳树，它适用于联通集合中的所有点。

对于斯坦纳树，从两方面考虑他，首先我们定义f[i][s]表示以i为根，联通状态为s的情况

对于更新，从两个方面考虑，第一个方面，根不变，枚举子集更新当前状态

第二个方面，子集不变，通过旁边的点来更新当前根

这两个的顺序不能改变，因为我们要保证在第二种情况更新的时候，当前联通所处的状态已经是最小值

对于为什么第二步更新必须存在但是只需要更新当前的状态呢。

有一个合理的解释是，因为更加后面的状态一定会从下一次的第一步来枚举更新出来。但是更新完后，当前状态并不一定是最小值

因为可能在真实的图上是有路径重叠的，因此我们可以通过其他额外的不在集合中的点来更新他。

对于第一步，使用状压dp，对于第二步，使用spfa来更新，因为第二步是一个三角不等式，可以进行松弛操作.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
typedef pair<int,pll> plll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int a[20][20];
int f[20][20][1050];
int st[20][20];
struct node{
    int a,b;
    int now;
}pre[20][20][1050];
queue<node> q;
int n,m;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void spfa(int state){
    while(q.size()){
        auto t=q.front();
        q.pop();
        st[t.a][t.b]=0;
        int i;
        for(i=0;i<4;i++){
            int x=t.a+dx[i];
            int y=t.b+dy[i];
            if(x&&x<=n&&y&&y<=m){
                if(f[x][y][state]>f[t.a][t.b][state]+a[x][y]){
                    f[x][y][state]=f[t.a][t.b][state]+a[x][y];
                    pre[x][y][state]={t.a,t.b,state};
                    if(!st[x][y]){
                        q.push({x,y,state});
                        st[x][y]=1;
                    }
                }
            }
        }
    }
}
void dfs(int a,int b,int state){
    if(!a||!b)
        return ;
    st[a][b]=1;
    auto x=pre[a][b][state];
    dfs(x.a,x.b,x.now);
    if(x.a==a&&x.b==b) dfs(x.a,x.b,state-x.now); //因为是从补集转移，因此另一边的补集也要查询
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i,j;
    int num=0;
    memset(f,0x3f,sizeof f);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
            if(!a[i][j]){
                f[i][j][1<<num]=0;
                num++;
            }
        }
    }
    int all=(1<<num)-1;
    for(int state=0;state<1<<num;state++){
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                for(int s=state;s;s=(s-1)&state){
                    if(f[i][j][state]>f[i][j][s]+f[i][j][state-s]-a[i][j]){
                        f[i][j][state]=f[i][j][s]+f[i][j][state-s]-a[i][j];
                        pre[i][j][state]={i,j,s};
                    }
                }
                if(f[i][j][state]<inf){
                    st[i][j]=1;
                    q.push({i,j,state});
                }
            }
        }
        spfa(state);
    }
    int ans=0x3f3f3f3f;
    int be=0,ed=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(f[i][j][all]<ans){
                ans=f[i][j][all];
                be=i,ed=j;
            }
        }
    }
    memset(st,0,sizeof st);
    dfs(be,ed,all);
    cout<<ans<<endl;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(!a[i][j]) cout<<"x";
            else{
                if(st[i][j]) cout<<"o";
                else cout<<"_";
            }
        }
        cout<<endl;
    }
    return 0;
}