自动搬运

查看原文

来自洛谷，原作者为

	Nangu 加 训

搬运于2025-08-24 21:15:04，当前版本为作者最后更新于2024-03-31 09:26:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

闲话：过了这道题后的好几个月，突然有人来问我这道题的解法，于是就有了这篇题解。

题意

给定一块 $n\times m$ 的方格，其中一些格子必须铺线，一些格子不能铺线，另一些可铺可不铺。要求：

• 电线联通。
• 不形成回路。

题解

这道题大概有以下几种方法：

1. 超纲并且难写的轮廓线DP
2. 正解但是难写的折半搜索
3. 难写的随机乱搞做法

反正都很难写就对了。

我们从起点开始走起。

40分做法：

爆搜即可。枚举每一个方格内放/不放电线，并在最终进行判断是否合法。我们需要实现一个搜索函数和一个判断电线合法的函数:

bool dfs2(int x, int y, int prex, int prey){
	if(vis[x][y]) return 0;//有回路
	--cnt, vis[x][y]=1;
	for(auto [tx, ty]:d){
		tx+=x, ty+=y;
		if(tx==prex && ty==prey || tx<1 || ty<1 || tx>n || ty>m || t[tx][ty]!='+') continue;
		if(!dfs2(tx, ty, x, y)) return 0;
	}
	return 1;
}

void dfs(int x, int y, int tot){
	if(y==m+1) ++x, y=1;
	memset(vis, 0, sizeof vis);
	if(x==n+1){
		cnt=tot;//cnt表示总电线数减去搜索到的电线数；若cnt!=0，则该图不连通
		bool flag=0;
		if(tot>res && dfs2(sx, sy, -1, -1) && !cnt){
			memcpy(ans, t, sizeof t);
			res=tot;
		}
		return;
	}
	if(s[x][y]!='#'){
		t[x][y]='+';
		dfs(x, y+1, tot+1);
		t[x][y]=s[x][y];
	} 
	if(s[x][y]!='+') dfs(x, y+1, tot);
}

100分做法：

观察上述程序，我们发现有很多地方可以剪枝优化：

• 因为题目要求的是最大值，故若当前答案已经不可能成为了最大值，直接返回。
• 若一处有回路，则不管其他地方填不填电线都不影响此处回路。因此，每一次填电线时，我们就进行一次判断判断，若填此电线会造成回路，则直接返回。

改良后的代码：

bool dfs2(int x, int y, int prex, int prey){
	if(vis[x][y]) return 0;
	--cnt, vis[x][y]=1;
	for(auto [tx, ty]:d){
		tx+=x, ty+=y;
		if(tx==prex && ty==prey || tx<1 || ty<1 || tx>n || ty>m || t[tx][ty]!='+') continue;
		if(!dfs2(tx, ty, x, y)) return 0;
	}
	return 1;
}

void dfs(int x, int y, int tot){
	if(y==m+1) ++x, y=1;
	if(0.8*((n-x)*m+m-y+1)+tot<=res) return;//1
	memset(vis, 0, sizeof vis);
	if(x==n+1){
		cnt=tot;
		bool flag=0;
		if(dfs2(sx, sy, -1, -1) && !cnt){
			memcpy(ans, t, sizeof t);
			res=tot;
		}
		return;
	}
	if(s[x][y]!='#'){
		t[x][y]='+';
		if(dfs2(x, y, -1, -1)) //2
			dfs(x, y+1, tot+1);
		t[x][y]=s[x][y];
	} 
	if(s[x][y]!='+') dfs(x, y+1, tot);
}

于是，我们就用简洁好写的剪枝搜索通过了这道题。