学弟@lher在周末训练赛中出的题目的原题(这个人拿省选题来当作提高组模拟,太丧了。。。)

题意简析:看题目:)

解题思路:题目显然是最大流。

首先拆点将点权变为边权,然后按照题意对于所有有跳板的点向可以跳到的点连一条权值为inf的边,对于能够跳出地图边界的点,将它与汇点连一条权值为inf的边。对于有蜥蜴的点,从源点向这个点连一条权值为1的边,然后跑一次最大流,答案就是蜥蜴数-最大流。

AC代码:

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
#define inf 0x7fffffff
using namespace std;
struct zxy{
int next,to,v;
}edge[];
int n,m,d,head[],iter[],lev[],que[],cnt=,mz=;
bool b[][];
inline int getno(int x,int y){ return (x-)*m+y;}
inline int getdis(int x,int y,int a,int b){ return ceil(sqrt((x-a)*(x-a)+(y-b)*(y-b)));}
inline void ins(int x,int y,int l){edge[++cnt].next=head[x],head[x]=cnt,edge[cnt].to=y,edge[cnt].v=l;}
inline int in(){
int x=,f=;
char ch=getchar();
while(ch<''||ch>'') {if(ch=='-') f=-; ch=getchar();}
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline bool bfs(int s,int e){
memset(lev,-,sizeof(lev));
int t=,h=;
que[]=s;
lev[s]=;
do{
h++;
int k=head[que[h]];
while(k){
if (lev[edge[k].to]==-&&edge[k].v){
lev[edge[k].to]=lev[que[h]]+;
que[++t]=edge[k].to;
}
k=edge[k].next;
}
}while(h<t);
return lev[e]!=-;
}
inline int dfs(int u,int v,int f){
if (u==v) return f;
int used=,k=head[u];
while(k){
if (edge[k].v&&lev[edge[k].to]==lev[u]+){
int w=dfs(edge[k].to,v,min(edge[k].v,f-used));
used+=w;
edge[k].v-=w;
edge[k^].v+=w;
if (used==f) return used;
}
k=edge[k].next;
}
return used;
}
int dinic(int s,int t){
int flow=;
while(bfs(s,t))
flow+=dfs(s,t,inf);
return flow;
}
void init(){
n=in(),m=in(),d=in();
for (int i=; i<=n; ++i){
for (int j=; j<=m; ++j){
int x=getchar()-'',no=getno(i,j);
if (x) ins(no,no+n*m,x),ins(no+n*m,no,),b[i][j]=;
}
getchar();
}
for (register int i=; i<=n; ++i){
for(register int j=; j<=m; ++j)
if (getchar()=='L') ++mz,ins(,getno(i,j),),ins(getno(i,j),,);
getchar();
}
for (register int i=; i<=n; ++i)
for (register int j=; j<=m; ++j)
if(b[i][j]){
if (i-d<||i+d>n||j-d<||j+d>m) ins(getno(i,j)+n*m,n*m*+,inf),ins(n*m*+,getno(i,j)+n*m,);
for (int k=(i-d<?:i-d); k<=(i+d>n?n:i+d); ++k)
for (int t=(j-d<?:j-d); t<=(j+d>m?m:j+d); ++t)
if (b[k][t]&&getdis(i,j,k,t)<=d&&(i!=k||j!=t))
ins(getno(i,j)+n*m,getno(k,t),inf),ins(getno(k,t),getno(i,j)+n*m,);
}
}
int main(){
init();
printf("%d",mz-dinic(,*n*m+));
return ;
}

本文由Melacau编写,Melacau代表M星向您问好,如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文,请您向我联系,email:13960948839@163.com.

最新文章

  1. 从客户端(Content=&quot;&lt;EM &gt;&lt;STRONG &gt;&lt;U &gt;这是测试这...&quot;)中检测到有潜在危险的Request.Form 值。
  2. Javascript 语言精粹 代码片段合集
  3. tomcat下iims的配置感悟
  4. appium跑demo简单实例讲解
  5. windows命令行及批处理文件小结
  6. Error Domain=kCLErrorDomain Code=0 &quot;The operation couldn’t be completed.
  7. jquery基础教程读书总结
  8. Real-Rime Rendering (2) - 变换和矩阵(Translation and Matrics)
  9. CodeForces 567C Geometric Progression 类似dp的递推统计方案数
  10. MongoDB--数据库与Collection注意事项
  11. 一张脑图说清 Nginx 的主流程
  12. MySQL单向加密函数
  13. logging模块全总结
  14. JS怎样实现图片的懒加载以及jquery.lazyload.js的使用
  15. POI Excel 单元格内容类型判断并取值
  16. MVC 带扩展名的路由无法访问
  17. SmileyCount.java笑脸加法程序代写(QQ:928900200)
  18. java使用DateUtils对日期进行运算
  19. vue问题总结
  20. 阿里云容器服务区块链解决方案全新升级 支持Hyperledger Fabric v1.1

热门文章

  1. 20162311 实验二 Java面向对象程序设计 实验报告
  2. 如何减小ios安装包大小
  3. 201621123043 《Java程序设计》第1周学习总结
  4. vue2.X简单翻页/分页
  5. 基于ssm的poi反射bean实例
  6. python3+beautifulSoup4.6抓取某网站小说(四)多线程抓取
  7. emqtt 试用(五)emq 的用户密码认证
  8. 敏捷项目需求拆解&amp;发现用户故事
  9. spring9——AOP之AspectJ对AOP的实现
  10. js中的caller属性和callee属性