「题解」「WC2008」游览计划 trip

WC2008 T1,斯坦纳树的例题。

题目链接:Luogu 4294/BZOJ 2595/WC2008 T1。

题目

题目描述

从未来过绍兴的小 D 有幸参加了 Winter Camp 2008,他被这座历史名城的秀丽风景所吸引,强烈要求游览绍兴及其周边的所有景点。

主办者将绍兴划分为 \(N\) 行 \(M\) 列个分块,如下图:

WC2008-T1 Z1

景点含于方块内,且一个方块至多有一个景点。无景点的方块视为路。

为了保证安全与便利,主办方依据路况和治安状况,在非景点的一些方块内安排不同数量的志愿者;在景点内聘请导游(导游不是志愿者)。在选择旅游方案时,保证任意两个景点之间,存在一条路径,在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要,又能够让志愿者的总数最少。

例如,在上面的例子中,在每个没有景点的方块中填入一个数字,表示控制该方块最少需要的志愿者数目:

WC2008-T1 Z2

图中用深色标出的方块区域就是一种可行的志愿者安排方案,一共需要 $20$ 名志愿者。由图可见,两个相邻的景点是直接(有景点内的路)连通的(如沈园和八字桥)。

现在,希望你能够帮助主办方找到一种最好的安排方案。

数据范围

数据点编号\(n\)\(m\)\(k\)
\(1\)\(\leq 2\)\(\leq 2\)\(\leq 2\)
\(2\)\(\leq 4\)\(\leq 5\)\(\leq 4\)
\(3\)\(\leq 2\)\(\leq 10\)\(\leq 3\)
\(4\)\(\leq 6\)\(\leq 7\)\(\leq 5\)
\(5\)\(\leq 8\)\(\leq 9\)\(\leq 7\)
\(6\)\(\leq 10\)\(\leq 9\)\(\leq 10\)
\(7\)\(\leq 9\)\(\leq 10\)\(\leq 10\)
\(8\)\(\leq 10\)\(\leq 10\)\(\leq 3\)
\(9\)\(\leq 10\)\(\leq 10\)\(\leq 10\)
\(10\)\(\leq 10\)\(\leq 10\)\(\leq 10\)

时空限制

题目编号时间限制空间限制
Luogu P4294\(1\text{s}\)\(125\text{MiB}\)
BZOJ 2595\(10\text{s}\)\(256\text{MiB}\)

题解

前置知识

思路

\(\text{dp}_{i,S}\) 表示以 \(i\) 号节点为根,当前状态为 \(S\) 的最小志愿者数。

当根 \(i\) 不改变时(即合并两个都包含 \(i\) 的联通块)状态转移方程是:

$$\text{dp}_{i,S}=\min_{s\subset S}\{\text{dp}_{i,s}+\text{dp}_{i,S-s}-\text{val}_i\}$$

其中 \(\text{val}_i\) 表示本题中 \(i\) 号点的权值。

当根改变时(即在原有联通块中加入一个新节点i并设置为根,要求i、k相邻):

$$\text{dp}_{i,S}=\min\{\text{dp}_{k,S}+\text{val}_i\}$$

斯坦纳树处理即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=10+5;
const int MAXM=10+5;
const int MAXNM=MAXN*MAXM;
const int MAXK=10+1;

int n,m,nm;
bool ans[MAXN][MAXM];
int a[MAXNM];

struct Node{
	int x,y,dis;
	inline Node(reg int x=0,reg int y=0,reg int dis=0):x(x),y(y),dis(dis){
		return;
	}
	inline bool operator<(const Node& a)const{
		return dis<a.dis;
	}
	inline bool operator>(const Node& a)const{
		return dis>a.dis;
	}
};

inline int GetID(reg int x,reg int y){
	return x*m+y;
}

inline bool check(reg int x,reg int y){
	return 0<=x&&x<n&&0<=y&&y<m;
}

bool vis[MAXNM];
int dp[MAXNM][1<<MAXK];
int pre[MAXNM][1<<MAXK][2];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;

inline void Dijkstra(int S){
	memset(vis,false,sizeof(vis));
	while(!Q.empty()){
		reg int x=Q.top().x,y=Q.top().y;
		int id=GetID(x,y);
		Q.pop();
		vis[GetID(x,y)]=true;
		const int dx[]={-1,0,0,1};
		const int dy[]={0,-1,1,0};
		for(reg int i=0;i<4;++i){
			reg int fx=x+dx[i],fy=y+dy[i];
			if(check(fx,fy)){
				reg int v=GetID(fx,fy);
				if(dp[v][S]>dp[id][S]+a[v]){
					dp[v][S]=dp[id][S]+a[v];
					pre[v][S][0]=id,pre[v][S][1]=S;
					Q.push(Node(fx,fy,dp[v][S]));
				}
			}
		}
	}
	return;
}

inline void DFS(reg int x,reg int y,reg int S){
	reg int id=GetID(x,y),v=pre[id][S][0],s=pre[id][S][1];
	if(!s)
		return;
	ans[x][y]=true;
	if(v==id)
		DFS(x,y,S^s);
	DFS(v/m,v%m,s);
	return;
}

int main(void){
	n=read(),m=read(),nm=n*m;
	memset(dp,0X3F,sizeof(dp));
	reg int root,k=0;
	for(reg int i=0,tot=0;i<n;++i)
		for(reg int j=0;j<m;++j,++tot){
			a[tot]=read();
			if(!a[tot])
				dp[tot][1<<(k++)]=0,root=tot;
		}
	for(reg int S=1;S<(1<<k);++S){
		for(int i=0;i<nm;++i){
			for(int sub=S&(S-1);sub;sub=S&(sub-1))
				if(dp[i][S]>dp[i][sub]+dp[i][S^sub]-a[i]){
					dp[i][S]=dp[i][sub]+dp[i][S^sub]-a[i];
					pre[i][S][0]=i,pre[i][S][1]=sub;
				}
			if(dp[i][S]!=INF)
				Q.push(Node(i/m,i%m,dp[i][S]));
		}
		Dijkstra(S);
	}
	printf("%d\n",dp[root][(1<<k)-1]);
	DFS(root/m,root%m,(1<<k)-1);
	for(reg int i=0,tot=0;i<n;++i){
		for(reg int j=0;j<m;++j)
			if(!a[tot++])
				putchar('x');
			else
				putchar(ans[i][j]?'o':'_');
		putchar('\n');
	}
	return 0;
}