[BZOJ2595][WC2008] 游览计划

试题分析

斯坦纳树裸题。
什么是斯坦纳树呢？就是求一类生成树，用如下dp方程即可求解：
(f_{i,j})表示点(i)与其它的关键点连通性为(j)的最小花费。

[f_{i,j}=f_{i,s}+f_{i,joplus s} (sin j) ]

[f_{i,j}=f_{k,j}+Cost_{i,k} ]

不难发现，如果把两维独立的话，那么上面就是层之间的转移。
下面就是一个层之内的松弛操作，用最短路松弛即可解决。

 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
#define LL long long
 
inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int INF = 1007483600;
const int MAXN = 100010;
 
int N,M; struct Mx{int x,y; Mx(int xx=0,int yy=0){x=xx; y=yy;}}; queue<Mx> que; 
struct Pos{int x,y,Grz; Pos (int xx=0,int yy=0,int Grzz=0){x=xx; y=yy; Grz=Grzz;} };
int f[11][11][(1<<11)];Pos g[11][11][(1<<11)]; bool vis[11][11];
int dis[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; int a[11][11];
 
inline void SPFA(int t){
    while(!que.empty()){
        Mx k=que.front(); que.pop(); vis[k.x][k.y]=false;
        for(int i=0;i<4;i++){
            int xx=k.x+dis[i][0],yy=k.y+dis[i][1];
            if(xx<1||xx>N||yy<1||yy>M) continue;
            if(f[xx][yy][t]>f[k.x][k.y][t]+a[xx][yy]){
                f[xx][yy][t]=f[k.x][k.y][t]+a[xx][yy];
                g[xx][yy][t]=Pos(k.x,k.y,t);
                if(!vis[xx][yy]) vis[xx][yy]=true,que.push(Mx(xx,yy));
            }
        }
    } return ;
}
inline void dfs(int x,int y,int t){
    if(!x||!y||!t) return ; vis[x][y]=true;
    dfs(g[x][y][t].x,g[x][y][t].y,g[x][y][t].Grz);
    if(g[x][y][t].x==x&&g[x][y][t].y==y) 
        dfs(g[x][y][t].x,g[x][y][t].y,t-g[x][y][t].Grz);
}
int x[11],y[11],C;
 
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    N=read(),M=read();
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++) {
            a[i][j]=read();
            if(!a[i][j]) x[++C]=i,y[C]=j;
        }
    } for(int i=0;i<=N;i++){
        for(int j=0;j<=M;j++)
            for(int k=0;k<(1<<C);k++) f[i][j][k]=INF;
    }
    for(int i=1;i<=C;i++) f[x[i]][y[i]][(1<<(i-1))]=0;
    for(int Grz=1;Grz<(1<<C);Grz++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                for(int k=Grz;k;k=(k-1)&Grz){
                    if(f[i][j][Grz]>f[i][j][Grz^k]+f[i][j][k]-a[i][j]){
                        f[i][j][Grz]=f[i][j][Grz^k]+f[i][j][k]-a[i][j];
                        g[i][j][Grz]=Pos(i,j,k);
                    }
                } if(f[i][j][Grz]<INF) que.push(Mx(i,j)),vis[i][j]=true;
            }
        } SPFA(Grz);
    } printf("%d
",f[x[1]][y[1]][(1<<C)-1]);
    memset(vis,false,sizeof(vis)); dfs(x[1],y[1],(1<<C)-1);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(!a[i][j]) putchar('x');
            else if(vis[i][j]) putchar('o');
            else putchar('_');
        } puts("");
    }
    return 0;
}