时间戳

首页 > 技术文章 > 浅谈斯坦纳树 && [WC2008]游览计划题解

浅谈斯坦纳树 && [WC2008]游览计划题解

hzf29721 2019-03-09 16:43 原文

Ⅰ、抛出问题

题目描述

从未来过绍兴的小D有幸参加了Winter Camp 2008，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。
主办者将绍兴划分为\(N\)行\(M\)列\((N×M)\)个分块，如下图\((8×8)\)：

景点含于方块内，且一个方块至多有一个景点。无景点的方块视为路。
为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的志愿者；在景点内聘请导游（导游不是志愿者）。在选择旅游方案时，保证任意两个景点之间，存在一条路径，在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要，又能够让志愿者的总数最少。
例如，在上面的例子中，在每个没有景点的方块中填入一个数字，表示控制该方块最少需要的志愿者数目：

图中用深色标出的方块区域就是一种可行的志愿者安排方案，一共需要20名志愿者。由图可见，两个相邻的景点是直接（有景点内的路）连通的（如沈园和八字桥）。
现在，希望你能够帮助主办方找到一种最好的安排方案。

Input

第一行有两个整数，N和M，描述方块的数目。
接下来N行，每行有M个非负整数，如果该整数为0，则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，
行首行末也可能有多余的空格。

Output

第一行有两个整数，N和M，描述方块的数目。
接下来N行，每行有M个非负整数，如果该整数为0，则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，
行首行末也可能有多余的空格。

Sample Input

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

Sample Output

xoox
___o
___o
xoox

HINT

所有的 10 组数据中 N, M ，以及景点数 K 的范围规定如下
输入文件中的所有整数均不小于 0 且不超过 2^16
感谢@panda_2134 提供Special Judge

Ⅱ、分析问题

斯坦纳树，用于解决一类生成树问题，如在图上做最小生成树，使得每个目标点互相联通的这种题
对于此题，设\(dp[i][sta]\)表示在\(i\)号节点，与目标点的连通性为\(sta\)的最小花费
则有

\[dp[i][sta]=min_{s\in sta} \{dp[i][s]+dp[i][sta\otimes s]-val[i]\} \]

大意为\(s\)为\(sta\)的子集，\(dp[i][sta]\)的值则等于其两个互补的子集之和，因为\(i\)号节点算了两次，所以最后要减去一个\(val[i]\)，表示减去加入\(i\)号点所需的花费
同时，还有状态转移方程

\[dp[i][sta]=\min\{dp[j][sta]+val[i](i\to j)\} \]

表示\(j\)与目标点的连通性为\(sta\)，即再连一条\(i\to j\)的边即可让\(i\)与目标点的连通性变为\(sta\)
第二个状态转移方程用SPFA暴力更新即可

#include<bits/stdc++.h>
#define F(i,j,n) for(register int i=j;i<=n;i++)
#define INF 0x3f3f3f3f
#define ll long long
#define mem(i,j) memset(i,j,sizeof(i))
#define pii pair<int,int>
using namespace std;
struct hahaha{
	int x,y,sta;
}pre[20][20][1050];
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//位移数组
int n,m,mp[50][50],cnt=0,f[50][50][2050],lx,ly;//本题中点的标号按坐标存，即(i,j)表示第一维
queue<pii>q;//SPFA队列
bool vis[50][50];//(i,j)这个点是否走过
inline int read(){
    int datta=0;char chchc=getchar();bool okoko=0;
    while(chchc<'0'||chchc>'9'){if(chchc=='-')okoko=1;chchc=getchar();}
    while(chchc>='0'&&chchc<='9'){datta=datta*10+chchc-'0';chchc=getchar();}
    return okoko?-datta:datta;
}
inline void SPFA(int now_sta){
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		vis[x][y]=0;
		F(p,0,3){
			int tx=x+dx[p],ty=y+dy[p];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
				if(f[tx][ty][now_sta]>f[x][y][now_sta]+mp[tx][ty]){
					f[tx][ty][now_sta]=f[x][y][now_sta]+mp[tx][ty];//转移
					pre[tx][ty][now_sta].x=x;
					pre[tx][ty][now_sta].y=y;
					pre[tx][ty][now_sta].sta=now_sta;//记录一下有哪个状态转移而来，方便处理第二问
					if(!vis[tx][ty])
						vis[tx][ty]=1,q.push(make_pair(tx,ty));
				}
			}
		}
		q.pop();
	}
}
inline void dfs(int x,int y,int sta){
	if(!pre[x][y][sta].x&&!pre[x][y][sta].y)//如果没有，说明走到了一条分支的尽头，return
		return ;
	vis[x][y]=1;//标记走过
	if(pre[x][y][sta].x==x&&pre[x][y][sta].y==y)//如果是由(x,y)位置的另一个状态转移而来(即主函数里的转移)
		dfs(x,y,sta^pre[x][y][sta].sta);//递归寻找补集
	dfs(pre[x][y][sta].x,pre[x][y][sta].y,pre[x][y][sta].sta);//寻找周围节点(即SPFA中的转移)
}
int main(){
	mem(f,0x3f);
	n=read();m=read();
	F(i,1,n)
		F(j,1,m){
			mp[i][j]=read();
			if(!mp[i][j])
				f[i][j][1<<(cnt++)]=0,lx=i,ly=j;//随便记录一个标记点记做(lx,ly)
		}
	F(sta,0,(1<<cnt)-1){//枚举联通状态
		F(i,1,n){
			F(j,1,m){//枚举坐标
				for(int s=sta;s;s=(s-1)&sta){//枚举子集
					if(f[i][j][sta]>f[i][j][s]+f[i][j][s^sta]-mp[i][j]){
						f[i][j][sta]=f[i][j][s]+f[i][j][s^sta]-mp[i][j];//转移
						pre[i][j][sta].x=i;
						pre[i][j][sta].y=j;
						pre[i][j][sta].sta=s;//记录由哪个状态转移而来
					}
				}
				if(f[i][j][sta]<0x3f3f3f3f)
					q.push(make_pair(i,j)),vis[i][j]=1;//如果有值，加入SPFA更新队列
			}
		}
		SPFA(sta);//SPFA暴力更新周围节点
	}
	mem(vis,0);
	printf("%d\n",f[lx][ly][(1<<cnt)-1]);//第一问
	dfs(lx,ly,(1<<cnt)-1);//寻找走了哪些点
	F(i,1,n)
		F(j,1,m){
			if(!mp[i][j])//如果是障碍物
				printf("x");
			else
				printf("%c",vis[i][j]==1?'o':'_');//走过就o,没走过就_
		printf("\n");
	}
    return 0;
}

推荐阅读