[WC2008]游览计划

斯坦纳树板子题，其实就是状压dp

令\(dp_{i,s}\)表示任意点\(i\)联通关键点集合\(s\)的最小代价

然后有转移
\[ dp_{i,S}=\min_{T\in S}dp_{i,S}+dp_{i,S \ xor\ T}-cost_i \]
这是自己转移自己
\[ dp_{u,S}=\min_{(u,v)\in E}dp_{v,S}+cost_u \]
这是从别人转移

我们按\(S\)分层去做，注意到别人转移是无后效性的，但长的像松弛，直接跑spfa就可以了

Code:

#include <cstdio>
#include <cstring>
#include <queue>
const int inf=0x3f3f3f3f;
int n,m,k,dp[11][11][1<<10],cost[11][11],vis[11][11];
struct node
{
    int x,y,s;
    node(){}
    node(int X,int Y,int S){x=X,y=Y,s=S;}
}pre[11][11][1<<10];
#define mp(a,b) std::make_pair(a,b)
std::queue <std::pair <int,int> > q;
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
void spfa(int s)
{
    while(!q.empty())
    {
        int x=q.front().first,y=q.front().second;
        q.pop();
        vis[x][y]=0;
        for(int i=1;i<=4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx&&ty&&tx<=n&&ty<=m&&dp[tx][ty][s]>dp[x][y][s]+cost[tx][ty])
            {
                dp[tx][ty][s]=dp[x][y][s]+cost[tx][ty];
                pre[tx][ty][s]=node(x,y,s);
                if(!vis[tx][ty]) q.push(mp(tx,ty)),vis[tx][ty]=1;
            }
        }
    }
}
void dfs(int x,int y,int s)
{
    if(!x||!y||!s) return;
    vis[x][y]=1;
    int tx=pre[x][y][s].x,ty=pre[x][y][s].y,t=pre[x][y][s].s;
    dfs(tx,ty,t^s);
    dfs(tx,ty,t);
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&cost[i][j]);
            if(cost[i][j]) dp[i][j][0]=cost[i][j];
            else dp[i][j][1<<k++]=0;
        }
    for(int s=1;s<1<<k;s++)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                for(int t=s;t;t=t-1&s)
                    if(dp[i][j][s]>dp[i][j][t]+dp[i][j][s^t]-cost[i][j])
                    {
                        dp[i][j][s]=dp[i][j][t]+dp[i][j][s^t]-cost[i][j];
                        pre[i][j][s]=node(i,j,t);
                    }
                if(dp[i][j][s]<inf) q.push(mp(i,j)),vis[i][j]=1;
            }
        spfa(s);
    }
    int tx=0,ty=0,s=(1<<k)-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(dp[i][j][s]<dp[tx][ty][s])
                tx=i,ty=j;
    printf("%d\n",dp[tx][ty][s]);
    dfs(tx,ty,s);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            putchar(vis[i][j]?(cost[i][j]?'o':'x'):'_');
        putchar('\n');
    }
    return 0;
}

2019.2.26

[WC2008]游览计划 解题报告

原文：https://www.cnblogs.com/butterflydew/p/10435953.html