BZOJ2595: [Wc2008]游览计划 斯坦纳树

思路:

斯坦纳树裸题.

输出方案的话记录一下转移就好了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x1f1f1f1f
 
#define N 11
#define M 11
int n,m,d[N][M],lab[N][M],cnt;
 
int f[N][M][1<<11];
 
struct Lastans{
    int x,y,S;
    Lastans(){}
    Lastans(int _x,int _y,int _S):x(_x),y(_y),S(_S){}
}g[N][M][1<<11];
 
struct Ins{
    int x,y;
    Ins(){}
    Ins(int _x,int _y):x(_x),y(_y){}
};
queue<Ins>q;
 
const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
bool inq[N][M];
#define Inrange(x,l,r) ((x)>=(l)&&(x)<=(r))
inline void spfa(int S){
    int tx,ty,i,j;
    while(!q.empty()){
        Ins t=q.front();q.pop();inq[i=t.x][j=t.y]=0;
        for(int k=0;k<4;++k)if(Inrange(tx=i+dx[k],1,n)&&Inrange(ty=j+dy[k],1,m)){
            if(f[tx][ty][S]>f[i][j][S]+d[tx][ty]){
                f[tx][ty][S]=f[i][j][S]+d[tx][ty],g[tx][ty][S]=Lastans(i,j,S);
                if(!inq[tx][ty])inq[tx][ty]=1,q.push(Ins(tx,ty));
            }
        }
    }
}
 
bool vis[N][M];
inline void dfs(int x,int y,int S){
    if(!S)return;
    vis[x][y]=1;if((!d[x][y])&&(S==(1<<lab[x][y])))return;
    Lastans p=g[x][y][S];
    dfs(p.x,p.y,p.S);
    if(S!=p.S)dfs(x,y,S-p.S);
}
 
int main(){
    scanf("%d%d",&n,&m);
    register int i,j;for(i=1;i<=n;++i)for(j=1;j<=m;++j){scanf("%d",&d[i][j]);if(!d[i][j])lab[i][j]=cnt++;}
    memset(f,0x1f,sizeof f);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!d[i][j])f[i][j][1<<lab[i][j]]=0;
    for(int S=1;S<(1<<cnt);++S){
        for(int mas=(S-1)&S;mas;mas=(mas-1)&S)
            for(i=1;i<=n;++i)
                for(j=1;j<=m;++j)
                    if(f[i][j][S]>f[i][j][mas]+f[i][j][S-mas]-d[i][j])
                        f[i][j][S]=f[i][j][mas]+f[i][j][S-mas]-d[i][j],g[i][j][S]=Lastans(i,j,mas);
        memset(inq,0,sizeof inq);
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(f[i][j][S]!=INF)q.push(Ins(i,j)),inq[i][j]=1;
        spfa(S);
    }
 
    Lastans res;
    int ans=INF;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ans>f[i][j][(1<<cnt)-1])ans=f[i][j][(1<<cnt)-1],res=Lastans(i,j,(1<<cnt)-1);
    printf("%d\n",ans);
    dfs(res.x,res.y,(1<<cnt)-1);
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j)if(!vis[i][j])putchar('_');else if(vis[i][j]&&d[i][j]==0)putchar('x');else putchar('o');puts("");
    }
    return 0;
}