BZOJ1412 ZJOI2009 狼和羊的故事


Description

“狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......” Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez发现狼和羊都有属于自己领地,若狼和羊们不能呆在自己的领地,那它们就会变得非常暴躁,不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地,再就是篱笆必须修筑完整,也就是说必须修建在单位格子的边界上并且不能只修建一部分。

Input

文件的第一行包含两个整数n和m。接下来n行每行m个整数,1表示该格子属于狼的领地,2表示属于羊的领地,0表示该格子不是任何一只动物的领地。

Output

文件中仅包含一个整数ans,代表篱笆的最短长度。

Sample Input

2 2
2 2
1 1

Sample Output

2
数据范围
10%的数据 n,m≤3
30%的数据 n,m≤20
100%的数据 n,m≤100


Dinic
考虑网络流建图
源点向gi,j=2连边
gi,j=1向汇点连边
gi,j=2向gi,j=1/0连边
gi,j=1向gi,j=1/0连边
然后我们只需要求出这张图的最小割就可以了


 #include<bits/stdc++.h>
using namespace std;
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define fv(a,b) for(int i=0;i<(signed)b.size();++i)
#define N 10010
#define INF 0x3f3f3f3f
struct Edge{int u,v,cap,flow;};
struct Dinic{
vector<Edge> E;
vector<int> G[N];
int S,T;
int d[N],vis[N];
void add(int u,int v,int cap){
E.push_back((Edge){u,v,cap,});
E.push_back((Edge){v,u,,});
int m=E.size();
G[u].push_back(m-);
G[v].push_back(m-);
}
bool bfs(){
memset(vis,,sizeof(vis));
memset(d,,sizeof(d));
queue<int> q;q.push(S);vis[S]=;
while(!q.empty()){
int u=q.front();q.pop();
fv(i,G[u]){
Edge e=E[G[u][i]];
if(!vis[e.v]&&e.cap>e.flow){
vis[e.v]=;
d[e.v]=d[u]+;
q.push(e.v);
}
}
}
return vis[T];
}
int dfs(int u,int a){
if(u==T||!a)return a;
int flow=;
fv(i,G[u]){
Edge &e=E[G[u][i]];
if(d[e.v]!=d[u]+)continue;
int f=dfs(e.v,min(a,e.cap-e.flow));
flow+=f;
a-=f;
e.flow+=f;
E[G[u][i]^].flow-=f;
if(!a)break;
}
if(!flow)d[u]=;
return flow;
}
int Max_flow(){
int flow=;
while(bfs())flow+=dfs(S,INF);
return flow;
}
}dinic;
#define M 110
int g[M][M],n,m;
int mx[]={,,-,};
int my[]={,-,,};
bool check(int x,int y){return !(x<||x>n||y<||y>m);}
int getind(int x,int y){return (x-)*m+y;}
int main(){
scanf("%d%d",&n,&m);
dinic.S=,dinic.T=N-;
fu(i,,n)fu(j,,m)scanf("%d",&g[i][j]);
fu(x,,n)fu(y,,m){
int id=getind(x,y);
if(g[x][y]==)dinic.add(id,dinic.T,INF);
if(g[x][y]==)dinic.add(dinic.S,id,INF);
if(g[x][y]==)continue;
fu(k,,){
int nx=x+mx[k];
int ny=y+my[k];
if(!check(nx,ny)||g[nx][ny]==)continue;
int nid=getind(nx,ny);
dinic.add(id,nid,);
}
}
printf("%d",dinic.Max_flow());
return ;
}

最新文章

  1. winform 多个label绑定一个事件
  2. markdown安装和使用
  3. onscroll事件的浏览器支持
  4. A daemon process class in python
  5. UVa 11181 条件概率
  6. HTML5 progress元素的样式控制、兼容与实例
  7. Tfs服务器迁移(更改IP)后客户端(vs2013)配置方法
  8. 一个技术汪的开源梦 —— 微信开发工具包(WeixinSDK)
  9. mac 安装mysql特种报错的对应解决方式
  10. php之冒泡排序
  11. Jdk1.7+eclipse搭建Java开发环境
  12. 关于springboot的定时器配置
  13. Linux、docker、kubernetes、MySql、Shell、kafka、RabbitMQ运维快餐
  14. 使用Fiddler测试WebApi接口
  15. 关于Quad PLL /CPLL参考时钟的选择
  16. RAC初步使用
  17. redis之事务
  18. SGU 275. To xor or not to xor (高斯消元法)
  19. JQuery中如何使用事件来出发Ajax
  20. Jmeter 接口测试-请求 Headers 与传参方式

热门文章

  1. springMvc REST 请求和响应
  2. CentOs64位编译安装hadoop-2.6.0
  3. RequestMaping url带参数及参数带“.&quot;的解决办法
  4. PHP运算符-算术运算符、三元运算符、逻辑运算符
  5. Pytorch CNN的各种参数
  6. python2.7安装requests
  7. Shell awk文本处理,shell脚本编写
  8. oracle 修改字符集 修改为ZHS16GBK
  9. CentOS 6.3从自带的Pyhon版本
  10. LeetCode OJ:Copy List with Random Pointer(复制存在随机链接的链表)