1066

思路:

  网络流最大流;

  拆点,每个点拆成两个,流量为这个点的高度;

  注意,文中说的距离是曼哈顿距离(劳资以为开根号wa了不知道多少次);

  每两个距离不大于d的点连边,流量inf;

  如果距离能够延伸到边界外,就将这个点连向t;

  最后输出,蜥蜴个数减去最大流;

来,上代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 905
#define INF 0x7ffffff struct NodeType {
int x,y,hi;
};
struct NodeType ai[maxn]; int n,m,cnt=,tot,map[maxn][maxn],s,t,que[maxn*maxn*],tott,d;
int head[maxn],deep[maxn],F[maxn*maxn*],E[maxn*maxn*],V[maxn*maxn*]; inline void edge_add(int u,int v,int f)
{
E[++cnt]=head[u],V[cnt]=v,F[cnt]=f,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,F[cnt]=,head[v]=cnt;
} bool bfs()
{
for(int i=s;i<=t;i++) deep[i]=-;
int h=,tail=;que[h]=s,deep[s]=;
while(h<tail)
{
int now=que[h++];
for(int i=head[now];i;i=E[i])
{
if(deep[V[i]]<&&F[i]>)
{
deep[V[i]]=deep[now]+;
if(V[i]==t) return true;
que[tail++]=V[i];
}
}
}
return false;
} int flowing(int now,int flow)
{
if(now==t||flow<=) return flow;
int oldflow=;
for(int i=head[now];i;i=E[i])
{
if(deep[V[i]]==deep[now]+&&F[i]>)
{
int pos=flowing(V[i],min(flow,F[i]));
F[i]-=pos,F[i^]+=pos;
flow-=pos,oldflow+=pos;
if(flow==) return oldflow;
}
}
if(oldflow==) deep[now]=-;
return oldflow;
} int main()
{
scanf("%d%d%d",&n,&m,&d);
char ch[];
for(int i=;i<=n;i++)
{
scanf("%s",ch+);
for(int j=;j<=m;j++)
{
if(ch[j]!='') ai[++tot].x=i,ai[tot].y=j,ai[tot].hi=ch[j]-'',map[i][j]=tot;
}
}
t=tot*+;
for(int i=;i<=tot;i++)
{
edge_add(i,i+tot,ai[i].hi);
for(int j=;j<=tot;j++)
{
if(j==i) continue;
if(abs(ai[i].x-ai[j].x)+abs(ai[i].y-ai[j].y)<=d) edge_add(i+tot,j,INF);
}
if(ai[i].x<=d||ai[i].y<=d||n-ai[i].x+<=d||m-ai[i].y+<=d) edge_add(i+tot,t,INF);
}
for(int i=;i<=n;i++)
{
scanf("%s",ch+);
for(int j=;j<=m;j++) if(ch[j]=='L') edge_add(s,map[i][j],),tott++;
}
int ans=;
while(bfs()) ans+=flowing(s,INF);
cout<<tott-ans;
return ;
}

最新文章

  1. C#语言和数据库基础
  2. Oracle 查询类似 select top 的用法
  3. python:open文件操作
  4. js 定时器的使用。 setInterval()
  5. ASDL + WN725N 配置无线AP
  6. TCP/IP 子网掩码浅析
  7. 2的32次方 分类: C#小技巧 2014-08-05 18:18 406人阅读 评论(0) 收藏
  8. polling轮询和comet
  9. Bruce Eckel的资源
  10. ListView之侧滑删除
  11. SQL给数据编号
  12. centos6 自带python2.6升级python2.7+
  13. Andorid开发(二十二)——获取上下文getApplicationContext()、Activity.this、 getBaseContext
  14. 2017-5-19&amp;5-23/系统性能指标
  15. 背水一战 Windows 10 (53) - 控件(集合类): ItemsControl 的布局控件 - ItemsStackPanel, ItemsWrapGrid
  16. Delphi下让窗口不显示在任务栏的另类方法
  17. 很简单的在Ubuntu系统下安装字体和切换默认字体的方法
  18. ubuntu14.04, libtinyxml.so.2.6.2: cannot open shared object file: No such file or directory
  19. Git——远程操作详解
  20. JFinal 3.3 入门学习 -- Hello JFinal World.

热门文章

  1. JAVA运行环境配置
  2. 笔记-python-__new__()
  3. VBA连接到SQL2008需要加上端口号
  4. 12,scrapy框架之post请求
  5. Django基于Pycharm开发之三[LANGUAGE_CODE与TIME_ZONE]
  6. [转]Git for windows 下vim解决中文乱码的有关问题
  7. axure rp教程(四)动态面板滑动效果
  8. python-day3-之函数
  9. hnust CZJ-Superman
  10. Map-Reduce基础