自动搬运

查看原文

来自洛谷，原作者为

	yuruilin2026 「形骸的残响に绊され灭びゆく都市を」|| INFP-T

搬运于2025-08-24 23:02:47，当前版本为作者最后更新于2024-12-02 19:57:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道 Hootime 看到就秒了的水紫。
本题解默认已经熟练掌握了匈牙利算法。
若没有，请移步 P3386。
话不多说，开始！

1. 题意：
   在地图内放机器人，只能在空地上放。
   除非有墙的阻隔，否则不能再同一行列中放机器人。
   求最多的机器人数量。

2. 思路：
   二分图秒了。
   用行列作为二分图的子图（应该是叫这个名字吧）。
   跑一遍匈牙利就行了。

3. 细节：
   建边的时候怎么办呢？

   如果没有墙，那么只需将行看作是二分图的一边，列看作另一边，然后可以放置机器人的地方的行向列连边即可。

   本来一行只能放一个机器人，但墙的出现导致一行被隔开，所以在有墙的情况下，可以把一行看成多行。

   还有！多测要清空！

那么，上代码！
代码里面有注释。

#include <bits/stdc++.h>
using namespace std;
#define int long long
char ch[1145][1145];
bool vis[1145][1145];
string str;
int g[114514],match[114514],re[114514],n,m,sum,next1[114514],head[114514],cnt;
int tot1,tot2;//左部点数量和右部点数量 
struct ppp{
	int d,x,y;
}a1[114514],a2[114514];
void add(int u,int p){ 
	++cnt;
	next1[cnt] = head[u],g[cnt] = p,head[u] = cnt;
}
bool dfs(int x){//匈牙利 
	for(register int i = head[x];i;i = next1[i]){//枚举右部点
		if(re[g[i]] == 0){//有边并且没被匹配 
			re[g[i]] = 1;//匹配上 
			if(match[g[i]] == 0){//match[i]存储的是匹配的人 
				match[g[i]] = x;
				return 1;
			}
			else if(dfs(match[g[i]])){
				match[g[i]] = x;
				return 1;
			}
		}
	}
	return 0;
}
void init(){
	for(register int i = 0;i <= 1143;++i) re[i] = 0;//re存储的是有没有被dfs过 
}
void init2(){//初始化(不得不说是真的恶心) 
	memset(vis,0,sizeof(vis));
	memset(g,0,sizeof(g));
	memset(match,0,sizeof(match));
	memset(re,0,sizeof(re));
	memset(next1,0,sizeof(next1));
	memset(head,0,sizeof(head));
	cnt = 0,tot1 = 0,tot2 = 0,sum = 0,n = 0,m = 0;
	for(register int i = 0;i <= 1513;++i){
		a1[i] = ppp{0,0,0};
		a2[i] = ppp{0,0,0};
	}
	for(register int i = 0;i <= 164;++i){
		for(register int j = 0;j <= 164;++j){
			ch[i][j] = ' ';
		}
	}
}
signed main(){
	cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	for(int ___ = 1;___ <= t;___++){
		init2();
		cin >> n >> m;
		for(register int i = 1;i <= n;i++){
			cin >> str;
			for(register int j = 1;j <= m;j++){
				 ch[i][j] = str[j-1];
			}
		}
		for(register int i = 1;i <= n;i++){
			for(register int j = 1;j <= m;j++){
				if(vis[i][j]) continue;
				if(ch[i][j] != 'o') continue;
				int xx11 = i,xx22 = i,yy11 = j,yy22 = j;
				while(xx11 > 1 && ch[xx11-1][j] != '#'){
					xx11--;//区间左端点 
				}
				while(xx22 < n && ch[xx22+1][j] != '#'){
					xx22++;//区间右端点 
				}
				for(register int k = xx11;k <= xx22;k++){
					vis[k][j] = 1;
				}
				a1[++tot1] = ppp{j,xx11,xx22};
			}
		}
		memset(vis,0,sizeof(vis));
		for(register int i = 1;i <= n;i++){
			for(register int j = 1;j <= m;j++){
				if(vis[i][j]) continue;
				if(ch[i][j] != 'o') continue;
				int xx11 = i,xx22 = i,yy11 = j,yy22 = j;
				while(yy11 > 1 && ch[i][yy11-1] != '#'){
					yy11--;//区间上端点 
				}
				while(yy22 < m && ch[i][yy22+1] != '#'){
					yy22++;//区间下端点 
				}
				for(register int k = yy11;k <= yy22;k++){
					vis[i][k] = 1;
				}
				a2[++tot2] = ppp{i,yy11,yy22};
			}
		}
		for(register int i = 1;i <= tot1;i++){
			for(register int j = 1;j <= tot2;j++){
				if(a1[i].x <= a2[j].d && a1[i].y >= a2[j].d){
					if(a2[j].x <= a1[i].d && a2[j].y >= a1[i].d){
						if(ch[a2[j].d][a1[i].d] == '*') continue;//交点是草不能建边 
						add(i,j);
					}
				}
			}
		}
		
		for(register int i = 1;i <= tot1;i++){
			init();
			if(dfs(i)) sum++;
		}
		cout << "Case :" << ___ << endl;
		cout << sum << endl;
	}
	return 0;
}