luogu3877 [TJOI2010]打扫房间

luogu3877 [TJOI2010]打扫房间

(​​* M的矩阵，每个房间的东南西北四面墙上都有一个门通向隔壁房间。另外有些房间是堆放杂物的，无需打扫。小A想设计若干条打扫路线，使得恰好进出每个需打扫的房间各一次，而且进出每个房间不能通过同一个门。要求每条路线都是一个闭合的环线，并且每条路线经过的房间数大于2。

如下面两图所示均为满足要求的打扫方案（灰色格子为放杂物的房间）：

小A发现对于某些房间布局是不存在这样的满足要求的方案的。他请你写一个程序计算一下，对于一种给定的房间布局，满足要求的方案是否存在。 输入输出格式

输入格式：

输入文件的第一行是一个整数T (1 ≤ T ≤ 10)，表示该文件中一共有T组数据。接下来依次是T组数据的信息。每组数据的第一行包含两个整数N和M，接下来的N行，每行包含M个字符，表示一个房间布局。字符’.’表示该房间需要打扫，’#’表示该房间是堆放杂物的，无需打扫。

输出格式：

共输出T行，对每组数据输出一行，为”YES”或”NO”，表示打扫方案存在与否。 输入输出样例 输入样例#1： 复制

4 3 4

..

…. …. 3 4

..

….

…

3 4

..

…

…

3 4

#

..

#

输出样例#1： 复制

YES NO YES NO

说明

对50%的数据，3 ≤ N,M ≤ 12

对100%的数据，3 ≤ N,M ≤ 30

每个测试点时限1秒 这题感觉和bzoj贪吃蛇那题有点像 但是确实是简化版的那题 考虑先针对这个棋盘进行黑白染色 然后因为要求能够构成环的话 我所有的格子应该都是满足度是2 一进一出 那么我先针对棋盘进行一下黑白格染色 然后我把黑点放在左边 白点放在右边 然后每个黑点都向周围的白点连1的点 从源点向每个黑点连权值为2的点 我可以把每个黑点的一进一出看作要发两条边 而白点的一进一出看成入两条边 每个白点向汇 连权值为2的点 然后这样 这样的话跑一下最大流 那么判断一下最大流是否满流即可 如果我可打扫的房间是奇数的话 那显然答案是不成立的

#include#include#include#include#define N 990#define inf 0x3f3f3f3fusing namespace std;char s[33][33];int dx[]={0,1,-1,0},dy[]={1,0,0,-1},h[N],level[N],T,id[33][33],num=1,TT,n,m;struct node{ int y,z,next;}data[32*N];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;}inline bool bfs(){ queueq;memset(level,0,sizeof(level));level[0]=1;q.push(0); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if (y==T) return 1; } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(s,z));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss; } }return ss-s;}int main(){ freopen("3877.in","r",stdin); scanf("%d",&TT); while(TT--){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%s",s[i]+1); memset(h,0,sizeof(h));num=1;int tot=0; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if(s[i][j]!='#') id[i][j]=++tot; // printf("%d\n",tot); if (tot&1) {printf("NO\n");continue;}T=tot+1;int sum=0; //printf("dafasd\n"); for (int i=1;i<=n;++i){ for (int j=1;j<=m;++j){ if (s[i][j]=='#') continue; if (i+j&1){ insert1(0,id[i][j],2);sum+=2; for (int k=0;k<4;++k){ int x1=i+dx[k],y1=j+dy[k]; if(x1<1||x1>n||y1<1||y1>m||s[x1][y1]=='#') continue; insert1(id[i][j],id[x1][y1],1); } }else{ insert1(id[i][j],T,2); } } }int ans=0;while(bfs()) ans+=dfs(0,inf); if (ans==sum) printf("YES\n");else printf("NO\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。