P4380 [USACO18OPEN]Multiplayer Moo S 题解

思路

第一问可以直接在给的地图上 Flood-Fill，可以 BFS 也可以并查集找连通块，时间复杂度差不多。

第二问比较难。首先可以想到的是暴力，对于一个连通块找与它相连的另一个连通块，然后试图把这两个连通块组合，每次去计算一下。

但时间复杂度非常高，所以考虑时间复杂度低的做法。接下来介绍这种做法。

1.1 第一步

既然要给连通块找与它相连的连通块，不妨把连通块看成一个点，然后对于它相连的连通块建无向边，这样就可以较快地知道它周围的连通块。由这些连通块得到的图上每个点存在点权，点权即为对应连通块的大小。

这一步可以放在解决第一问的时候顺便做。

注意要给每个连通块重新编号，否则对于两块属于同一人但分开的连通块，你的程序会认为是同一个连通块。

1.2 第二步

对于相邻的连通块建无向边后，你便可以在得到的图里，针对每一个连通块与它相邻的连通块做 BFS 算第二问的答案，可惜还是太慢了，所以考虑更改 BFS 的方式。

容易发现一种卡掉这种做法的输入：

250
1 2 1 2 1 2 ...
2 1 2 1 2 1 ...
1 2 1 2 1 2 ...
...

在这种输入里，每一个点 BFS 都会一直扩展到整个棋盘，因此我们的算法就被卡成了 \(O(N^4)\)，所以考虑更好的方法。

容易想到在这道题里，多次走重复的边没有任何意义，因此开一个 \(\texttt{map}\) 存边是否走过。

在避免走重复边的同时也要记录是否走了重复点。注意在这里 BFS 的时候，每次 BFS 前要清掉标记点的数组，而不要清掉标记边的数组。

在 BFS 内要写检查是否走到了重复边的代码，如果检查到了那么这次 BFS 没有意义，直接退出 BFS。

在每次 BFS 中，如果不能够再扩展且不是无意义的 BFS，则把 BFS 中遇到的连通块的大小求和最后和答案取 \(\max\)。

代码

前半部分将详细解释各部分代码的打法，后面一小部分会讲如何卡常通过 #9，#10，hack。

2.1 解决第一问

使用一个 \(\texttt{queue}\) 进行 BFS 找连通块，注意这里我们算出来的东西不只是连通块（务必仔细看它们的作用，第二问将非常依赖它们）：

• \(tnt\) 是编号，来一个新的连通块给一个新的编号。最终的编号是互不相同的。
• \(cnt\) 用于存储该位置所在连通块的编号。
• \(is\) 用于存储该编号下的连通块的实际值。
• \(num\) 用于存储该编号表示的连通块大小。

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		if(!vis[i][j]){
			int sum=0;
			vis[i][j]=1;
			q.push(mp(i,j));//初始化
			while(!q.empty()){
				sum++;
				int x=q.front().first;
				int y=q.front().second;
				cnt[x][y]=tnt;//告诉这个点所在连通块的编号
				q.pop();//记得 pop
				for(int p=0;p<4;p++){
					int yh=x+dx[p],hx=y+dy[p];
					if(yh>n||hx>n||yh<1||hx<1||vis[yh][hx]||a[yh][hx]!=a[x][y]){
						continue;
					}
					vis[yh][hx]=1; 
					q.push(mp(yh,hx));//记得 push
				}
			}
			num[tnt]=sum;//处理编号为 tnt 的连通块的大小
			is[tnt]=a[i][j];//处理编号为 tnt 的连通块的实际值
			tnt++;
			ans=max(ans,sum);
		}
	}
}
cout<

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		for(int p=0;p<4;p++){
			int yh=i+dx[p],hx=j+dy[p];
			if(yh>n||hx>n||yh<1||hx<1||cnt[yh][hx]==cnt[i][j]){
				continue;
			}
			if(mup.count(mp(cnt[i][j],cnt[yh][hx]))){
				continue;
			}
			vp[cnt[i][j]].push_back(cnt[yh][hx]);
			vp[cnt[yh][hx]].push_back(cnt[i][j]);
			mup[mp(cnt[i][j],cnt[yh][hx])]=mup[mp(cnt[yh][hx],cnt[i][j])]=1;
		}
	}
}

for(int i=1;i();
		q1.push(i);
		q1.push(tql);
        //在这里接 2.3.2 的程序
	}
}

while(!q1.empty()){
	int x=q1.front();
	q1.pop();
	for(int k=0;k

if(!f){
	ans2=max(ans2,sum);
}

if(!f){
	if(sum>=sq){
		cout<