[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]游览计划解题报告

[WC2008]游览计划

最新文章

热门文章

巴特西

[WC2008]游览计划 解题报告

[WC2008]游览计划

最新文章

热门文章

[WC2008]游览计划解题报告