[WC2008]游览计划 解题报告

时间:2021-08-01 12:54:03

[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