自动搬运

查看原文

来自洛谷，原作者为

	GNAQ Good:bye

搬运于2025-08-24 21:53:27，当前版本为作者最后更新于2019-01-22 20:26:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

拿下一血，补个题解吧。

二分图 × 博弈

这题实际上是 P4055 [JSOI2009]游戏 ←这货的三维 弱化不用求方案但是多组数据很恶心 版

然而就算是三维，照样可以黑白染色然后套二分图博弈模型。因为走法都是某种颜色的格子到异色的格子，所以二维的所有二分图博弈结论全部可以照搬过来。

然后就照着那个题做就行了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define ll long long
#define fst first
#define snd second
using namespace std;

int R,C,H,id[110][110][110],ids; bool ans;

int dx[6]={0,-1,0,1,0,0},dy[6]={-1,0,1,0,0,0},dz[6]={0,0,0,0,1,-1};

template<typename int_t>
void readx(int_t& x)
{
	x=0; int_t k=1; char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

// Bipartite graph matching
struct ed
{
	int pre,to;
}edge[4010];
int at,ptr[110];
vector<int> sts;
int visV[110],mat[110];

void Is(int fx,int tx)
{
	at++;
	edge[at].pre=ptr[fx];
	edge[at].to=tx;
	ptr[fx]=at;
	at++;
	edge[at].pre=ptr[tx];
	edge[at].to=fx;
	ptr[tx]=at;
}

bool Hungary(int now,int src)
{
	for (int v=ptr[now];v;v=edge[v].pre) if (visV[edge[v].to]!=src)
	{
		visV[edge[v].to]=src;
		if (!mat[edge[v].to] || Hungary(mat[edge[v].to],src)) { mat[edge[v].to]=now; return true; }
	}
	return false;
}

// Build Graph
struct _Node
{
	int x,y,z;
	_Node() {}
	_Node(int ix,int iy,int iz) { x=ix; y=iy; z=iz; }
};
queue<_Node>que; _Node cac;
bool vis[110];
void BFS_Build(_Node str)
{
	// Clear Graph
	at=1; memset(ptr,0,sizeof ptr); sts.clear();
	memset(visV,0,sizeof visV); memset(mat,0,sizeof mat);
	
	que.push(str); vis[id[str.x][str.y][str.z]]=1;
	while (!que.empty())
	{
		cac=que.front(); que.pop(); 
		int nx=cac.x,ny=cac.y,nz=cac.z,nid=id[nx][ny][nz];
		sts.push_back(nid);
		
		for (int w=0;w<6;w++) 
		{
			int tid=id[nx+dx[w]][ny+dy[w]][nz+dz[w]];
			if (!vis[tid]) // vis[0]=1!!
			{
				vis[tid]=1;
				que.push(_Node(nx+dx[w],ny+dy[w],nz+dz[w]));
			}
			if (tid && (nx+ny+nz)%2) Is(nid,tid);
		}
	}
}

void Solve()
{
	ids=0; ans=0; memset(vis,0,sizeof vis); vis[0]=1;
	memset(id,0,sizeof id);
	
	// read
	readx(H); readx(R); readx(C); char ch=0;
	for (int k=1;k<=H;k++)
		for (int i=1;i<=R;i++)
			for (int j=1;j<=C;j++)
			{
				ch=0; while (ch!='.' && ch!='X') ch=getchar();
				if (ch=='.') id[i][j][k]=++ids;
			}
			
	for (int i=1;i<=R;i++)
		for (int j=1;j<=C;j++)
			for (int k=1;k<=H;k++) if (id[i][j][k] && !vis[id[i][j][k]])
			{
				// Make bipartite graph
				BFS_Build(_Node(i,j,k)); 
				for (unsigned u=0;u<sts.size();u++) 
					if (!Hungary(sts[u],sts[u])) ans|=1;
			}
	printf(ans?"yes\n":"no\n");
}

int main()
{
	int T; readx(T);
	while (T--)
	{
		Solve();
	}
}