正解:网络流

解题报告:

传送门!

昂显然考虑最小割鸭$QwQ$,就考虑说每个土地要么属于羊要么属于狼,然后如果一条边上是栅栏一定是相邻两边所属不同.

所以考虑给所有羊向$S$连$inf$,所有狼向$T$连$inf$,然后相邻土地四联通之间连1就欧克了?

$over$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define t(i) edge[i].to
#define fy(i) edge[i].fy
#define w(i) edge[i].wei
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define e(i,x) for(ri i=head[x];~i;i=edge[i].nxt) const int N=+;
const int inf=1e9;
int ed_cnt=-,head[N],dep[N],S,T,cur[N],n,m,mvx[]={,,,-},mvy[]={,-,,};
struct ed{int to,nxt,wei;}edge[N]; 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 void ad(ri x,ri y,ri 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 int nam(ri x,ri y){return (x-)*m+y;}
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 dep[T];
}
il int dfs(ri nw,ri flow)
{
if(nw==T || !flow)return flow;ri ret=;
for(ri &i=cur[nw];~i;i=edge[i].nxt)if(w(i) && dep[t(i)]==dep[nw]+){ri tmp=dfs(t(i),min(flow,w(i)));flow-=tmp,w(i)-=tmp,ret+=tmp,w(i^)+=tmp;}
if(!ret)dep[nw]=;
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()
{
memset(head,-,sizeof(head));n=read();m=read();S=;T=n*m+;
rp(i,,n)rp(j,,m){ri tmp=read();if(tmp==)ad(nam(i,j),S,inf);if(tmp==)ad(T,nam(i,j),inf);}
rp(i,,n)
rp(j,,m)rp(k,,){ri tx=i+mvx[k],ty=j+mvy[k];if(tx && ty && tx<=n && ty<=m)ad(nam(i,j),nam(tx,ty),);}
printf("%d\n",dinic());
return ;
}

最新文章

  1. SQLAchemy
  2. jQuery 求页面加载等待特效
  3. AngularJS中的指令
  4. [译] 第三十天:Play Framework - Java开发者梦寐以求的框架 - 百花宫
  5. 图片lightbox2
  6. QGridLayout--01
  7. 解决 SVN cleanup 任务中断导致无法 update
  8. js获取页面高度赋值给div
  9. yii分页
  10. 第10课_dg
  11. Redis源代码分析(十)--- testhelp.h小测试框架和redis-check-aof.c 日志检测
  12. ElasticSearch 学习记录之ES短语匹配基本用法
  13. Eclipse调试(1)——基础篇
  14. vs code中文扩展包
  15. redis_哈希对象
  16. 如何理解php的依赖注入
  17. SqlServer_存储过程
  18. LeakCanary 原理浅析
  19. Opengl的gl_NormalMatrix
  20. 深入理解Java接口和抽象类

热门文章

  1. [翻译]Python中yield的解释
  2. Android Studio(九):引用jar及so文件
  3. 随机线性网络编码的C语言实现,实现可靠传输:实现篇(2)
  4. oracle CBO下使用更具选择性的索引
  5. Linux环境下第一次提交项目
  6. vue+element-ui 字体自适应不同屏幕
  7. Python--day42--mysql数据库--mysql前言
  8. 2018-8-10-如何入门-C++-AMP-教程
  9. 【codeforces 761D】Dasha and Very Difficult Problem
  10. 添加gitignore文件后使其生效