正解:网络流

解题报告:

传送门$QwQ$

昂考虑把题目的约束条件详细化?就说每个格点能向四连通连边,问能否做到每个格点度数等于2?

$umm$就先黑白染色建两排点呗,然后就$S$向左侧连流量为2的边右侧向$T$连流量为2的边,然后四连通之间连流量为1的边,跑个最大流看跑满没有,然后就做完了?$QwQ$

解释下趴还是,,,毕竟我之前没解释重新看一遍我题解都没想通$QAQ$

首先找出题目的所有约束条件$QwQ$

1)每个房间进出各一次

2)每扇门最多经过一次

3)环长大于2

昂条件一等价于每个点度数等于2嘛,然后其实有了条件二就一定能满足条件三鸭,所以现在就变成,每个点度数等于2,且相邻点之间最多经过一次.

所以就$ST$分别向点连流量为2的边相邻之间连流量为1的边就欧克了$QwQ$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define t(i) edge[i].to
#define w(i) edge[i].wei
#define n(i) edge[i].nxt
#define ri register int
#define rb register int
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];~i;i=n(i)) const int N=+,M=+,inf=1e9;
char str[M];
bool zt[M][M];
struct ed{int to,nxt,wei;}edge[N<<];
int n,m,dep[N],head[N],cur[N],S,T,ed_cnt=-,mvx[]={,,,-},mvy[]={,-,,},cnt; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il int nam(ri x,ri y){return (x-)*m+y;}
il void print(ri d)
{
if(!d)return void(printf("S"));if(d>n*m)return void(printf("T"));
ri y=d%m,x=d/m+;if(!y)y=m,--x;printf("(%d , %d)",x,y);
}
il void ad(ri x,ri y,ri z)
{//printf("%d -> %d : %d\n",y,x,z);
//print(y);printf(" -> ");print(x);printf(" : %d\n",z);
edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],};head[x]=ed_cnt;}
il bool bfs()
{
queue<int>Q;Q.push(S);memset(dep,,sizeof(dep));dep[S]=;
while(!Q.empty())
{
ri nw=Q.front();Q.pop();
e(i,nw)if(w(i) && !dep[t(i)]){dep[t(i)]=dep[nw]+,Q.push(t(i));if(t(i)==T)return ;}
}
return ;
}
il int dfs(ri nw,ri flow)
{
if(nw==T || !flow)return flow;ri ret=;
for(ri &i=cur[nw];~i;i=n(i))
if(w(i) && dep[t(i)]==dep[nw]+)
{ri tmp=dfs(t(i),min(flow,w(i)));ret+=tmp,w(i)-=tmp;w(i^)+=tmp,flow-=tmp;}
return ret;
}
il int dinic(){ri ret=;while(bfs()){rp(i,S,T)cur[i]=head[i];while(int d=dfs(S,inf))ret+=d;}return ret;} int main()
{
//freopen("3877.in","r",stdin);freopen("3877.out","w",stdout);
ri tmp=read();
while(tmp--)
{
ed_cnt=-;memset(head,-,sizeof(head));n=read();m=read();cnt=;
rp(i,,n){scanf("%s",str);rp(j,,m)cnt+=(zt[i][j]=str[j-]=='.');}S=;T=n*m+;
rp(i,,n)rp(j,,m)
{
if((i+j)& && zt[i][j])
rp(k,,)
{
ri tx=i+mvx[k],ty=j+mvy[k];
if(!tx || !ty || tx>n || ty>m)continue;
if(zt[tx][ty])ad(nam(tx,ty),nam(i,j),);
}
}
rp(i,,n)rp(j,,m)if(zt[i][j]){if((i+j)&)ad(nam(i,j),S,);else ad(T,nam(i,j),);}
if(cnt&){printf("NO\n");continue;}
if(dinic()==cnt)printf("YES\n");else printf("NO\n");
}
return ;
}

最新文章

  1. Win10下SQLServer2000的安装
  2. alibaba-dexposed 原理解析
  3. ReactNative win10初体验
  4. 在 C# 控制台中记录异常日志并输出
  5. Codeforces Round #271 (Div. 2) F ,E, D, C, B, A
  6. 常用命令su ls cp cd mv cat touch mkdir rm head less more pwd tac 等
  7. JAVA冒泡排序/JAVA冒泡排序再找出给定数据中的最大值最小值/JAVA数组排序
  8. MEF初体验之九:部件生命周期
  9. 在oracle中,group by后将字符拼接,以及自定义排序
  10. P2678 跳石头---(二分答案)
  11. Carmichael Numbers (Uva No.10006) -- 快速幂运算_埃氏筛法_打表
  12. Python——eventlet.wsgi
  13. 使用catch做单元测试简介
  14. Navicat连接mysql8出现1251错误
  15. POJO,简单的Java对象
  16. php serialize序列化对象或者数组
  17. BOM DOM区别 来源
  18. Vmware 安装CentOS7时连不上网问题的解决
  19. ORACLE 按表字段值的不同统计数量
  20. 紫书 习题 10-2 UVa 808(建立坐标+找规律)

热门文章

  1. Flask学习之三 web表单
  2. 洛谷P1049 装箱问题
  3. Bitmap的recycle问题
  4. Layout布局(补充)
  5. 全面理解Python中的类型提示(Type Hints)
  6. torch中的copy()和clone()
  7. ABSD 基于架构的软件设计方法方法简介(摘抄)
  8. css的一些小问题
  9. 2019-8-24-win10-uwp-读取文本GBK错误
  10. 【9001】Internet消息发布