Bzoj1189 [HNOI2007]紧急疏散evacuate_weixin_33717117的博客-程序员信息网

技术标签: c/c++  

1189: [HNOI2007]紧急疏散evacuate

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2293  Solved: 715

Description

发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域。每个格子如果是'.',那么表示这是一块空地;如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。

Input

输入文件第一行是由空格隔开的一对正整数N与M,3<=N <=20,3<=M<=20,以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D',且字符间无空格。

Output

只有一个整数K,表示让所有人安全撤离的最短时间,如果不可能撤离,那么输出'impossible'(不包括引号)。

Sample Input

5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX

Sample Output

3

HINT

 

2015.1.12新加数据一组,鸣谢1756500824


C++语言请用scanf("%s",s)读入!

 

Source

 

网络流,二分答案

将门拆点,每个门在每个时间对应一个点,从该点到汇点连一条容量为1的边,代表每单位时间可以出去一个人。

从原点向每个初始有人的点连一条容量为1的边。

二分花费时间,从每个有人的位置到限定时间内该位置能到达的门(预处理出最短距离)连一条容量为1的边,若最大流==人数,那么该时间可行。

 

↑因为看着数据挺小,用枚举答案代替了二分答案,这样做的好处是每次时间++,可以在原来的残量网络上加边,不需重构图。

  ↑但写出来还是不如二分快。

  ↑原来是我自己常数写挂了

 

  1 /*by SilverN*/
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<vector>
  8 #include<queue>
  9 using namespace std;
 10 const int INF=1e9;
 11 const int mx[5]={
    0,1,0,-1,0};
 12 const int my[5]={
    0,0,1,0,-1};
 13 const int mxn=45;
 14 struct edge{
 15     int v,nxt,f;
 16 }e[500010];
 17 int hd[mxn*mxn],mct=1;
 18 inline void add_edge(int u,int v,int c){
 19     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=c;hd[u]=mct;return;
 20 }
 21 inline void insert(int u,int v,int c){
 22     add_edge(u,v,c);add_edge(v,u,0);
 23     return;
 24 }
 25 vector<pair<int,int> >pos;
 26 char mp[mxn][mxn];
 27 int dis[mxn][mxn][mxn];
 28 int id[mxn][mxn],ict=0;
 29 int n,m,S,T;
 30 int tot=0,dr=0,ans=0;
 31 int d[mxn*mxn];
 32 bool BFS(){
 33     memset(d,0,sizeof d);
 34     queue<int>q;
 35     q.push(S);
 36     d[S]=1;
 37     while(!q.empty()){
 38         int u=q.front();q.pop();
 39         for(int i=hd[u];i;i=e[i].nxt){
 40             int v=e[i].v;
 41             if(!d[v] && e[i].f){
 42                 d[v]=d[u]+1;
 43                 q.push(v);
 44             }
 45         }
 46     }
 47     return d[T];
 48 }
 49 int DFS(int u,int lim){
 50     if(u==T)return lim;
 51     int tmp,f=0;
 52     for(int i=hd[u];i;i=e[i].nxt){
 53         int v=e[i].v;
 54         if(d[v]==d[u]+1 && e[i].f){
 55             tmp=DFS(v,min(lim,e[i].f));
 56             e[i].f-=tmp;
 57             e[i^1].f+=tmp;
 58             lim-=tmp;
 59             f+=tmp;
 60             if(!lim)return f;
 61         }
 62     }
 63     d[u]=0;
 64     return f;
 65 }
 66 int Dinic(){
 67     int res=0;
 68     while(BFS())res+=DFS(S,1e9);
 69     return res;
 70 }
 71 int main(){
 72     int i,j;
 73     scanf("%d%d",&n,&m);
 74     for(i=1;i<=n;i++)
 75         scanf("%s",mp[i]+1);
 76     S=0;T=1;ict=1;
 77     for(i=1;i<=n;i++)
 78      for(j=1;j<=m;j++){
 79          if(mp[i][j]=='X')continue;
 80          id[i][j]=++ict;
 81          if(mp[i][j]=='.'){
 82              tot++;
 83              pos.push_back(make_pair(i,j));
 84              insert(S,id[i][j],1);
 85         }
 86     }
 87     memset(dis,0x3f,sizeof dis);
 88     for(i=1;i<=n;i++)
 89         for(j=1;j<=m;j++){
 90             if(mp[i][j]=='D'){
 91                 dr++;
 92                 queue< pair<int,int> >q;
 93                 q.push(make_pair(i,j));
 94                 dis[dr][i][j]=0;
 95                 while(!q.empty()){
 96                     int x=q.front().first;
 97                     int y=q.front().second;
 98                     q.pop();
 99                     for(int k=1;k<=4;k++){
100                         int nx=x+mx[k];
101                         int ny=y+my[k];
102                         if(nx<1 || nx>n || ny<1 || ny>m)continue;
103                         if(mp[nx][ny]!='.')continue;
104                         if(dis[dr][nx][ny]>dis[dr][x][y]+1){
105                             dis[dr][nx][ny]=dis[dr][x][y]+1;
106                             q.push(make_pair(nx,ny));
107                         }
108                     }
109                 }
110             }
111         }
112     for(i=1;i<=tot*2;i++){
    //枚举时间 
113         if(i>1)    for(j=1;j<=dr;j++){
114             insert(ict+dr*(i-2)+j,ict+dr*(i-1)+j,INF);//在门边等待 
115         }
116         for(j=1;j<=dr;j++)
117             insert(ict+dr*(i-1)+j,T,1);//可以撤离一个人 
118         for(j=1;j<=dr;j++){
119             for(int k=0;k<pos.size();k++){
120                 int x=pos[k].first;
121                 int y=pos[k].second;
122                 if(mp[x][y]=='.' && dis[j][x][y]==i)
123                     insert(id[x][y],ict+dr*(i-1)+j,1);//移动到门边 
124             }
125         }
126         ans+=Dinic();
127         if(ans==tot){printf("%d\n",i);return 0;}
128     }
129     printf("impossible\n");
130     return 0;
131 }

 

转载于:https://www.cnblogs.com/SilverNebula/p/6189083.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_33717117/article/details/94495221

智能推荐

Docker命令之容器命令_zy010101的博客-程序员信息网

容器命令docker rundocker run会先找本地镜像,如果找不到,就自动去远程仓库拉取镜像(默认拉取latest版本),然后使用这个镜像来启动容器。命令详细格式如下:sudo docker run [OPTIONS] IMAGE [COMMAND] [ARG...]一般常用的OPTIONS有下面的几个。–name=“容器新名字” 为容器指定一个名称;-i:以交互模式运行容器,通常与 -t 同时使用;-t:为容器重新分配一个伪输入终端,通常与 -i 同时使用;也即启动

8、void 的意义_叫我谢布斯的博客-程序员信息网

1、void 修饰函数代表没有参数和没有返回值2、void不是实际的类型,而是一种抽象的类型。不能用void定义变量,但是可以用void 定义指针。比如:void a; //errorvoid p[5]; //error void *p; //正确可以定义void 类型的指针,因为指针都是固定4Byte(win32)...

springsecurity权限验证_成_蹉_跎的博客-程序员信息网

现在是大三暑假,有机会来到企业里面学习一些东西,在接触一段 spring boot 之后需要做权限验证,只是对登录用户的进行权限验证,将整理的内容和大家分享一下。看到的一些博客的内容:https://blog.csdn.net/UpdateAllTheTime/article/details/82664103https://www.cnblogs.com/rolandlee/p/958049...

05.Linux中挂载CentOS镜像以及配置本地yum源 超详细小白都能看懂_时空鱼的博客-程序员信息网

1.5 挂载 ios持有系统镜像 光驱因为 linux系统镜像中包含了常用的软件包, 就不用从网上下载了所以需要挂载 持有系统镜像 的 光驱第一种挂载方法1.5.1操作步骤1.点击设置进入到图片下面然后勾选框框里面的最后确定2.创建目录/mnt/cdrom输入lsblk -f查看是否查找sr0如果存在说明系统镜像在光驱中了进行下一个操作3.通过mount /dev/sr0 /...

jQuery选择器:nth-child(2) 与:nth-child(2n) 的区别_iteye_13003的博客-程序员信息网

// nth-child(2)$('table tr td:nth-child(2)').css('background-color','red'); // :nth-child(2n)$('table tr td:nth-child(2n)').css('background-color','red');   演示地址: http://qiaole.sina...

云文档能代替服务器吗,云存储能代替服务器存储吗_mogego七海的博客-程序员信息网

云存储能代替服务器存储吗 内容精选换一换本章节主要介绍云硬盘、弹性文件服务、对象存储服务等存储服务,让您更好的了解这些存储服务。使用存储容灾服务前,请您先了解表1中描述的使用限制。在生产站点可用区整个AZ故障时,可通过容灾演练功能恢复服务器业务。首次切换/故障切换和容灾演练操作后,登录弹性云服务器有哪些注意事项?云存储能代替服务器存储吗 相关内容ModelArts为用户提供了多种常见的预置引擎,但...

随便推点

目录遍历漏洞_Sakura0824的博客-程序员信息网_目录遍历漏洞修复

一. 什么是目录遍历漏洞目录遍历(路径遍历)是由于web服务器或者web应用程序对用户输入的文件名称的安全性验证不足而导致的一种安全漏洞,使得攻击者通过利用一些特殊字符就可以绕过服务器的安全限制,访问任意的文件(可以使web根目录以外的文件),甚至执行系统命令。二. 目录遍历漏洞原理程序在实现上没有充分过滤用户输入的../之类的目录跳转符,导致恶意用户可以通过提交目录跳转来遍历服务器上

CIM城市信息模型(City Information Modeling)_跃然实验室的博客-程序员信息网_城市信息模型

BIM是单体,CIM是群体,BIM是CIM的细胞。要解决智慧城市的问题,仅靠单个细胞的BIM还不够,需要大量细胞再加上各种连接网络构成的CIM才可以。CIM这个概念的提出,把视野从单体建筑拉高到建筑群和城市一级,给予智慧城市更加有力的支撑。在CIM中,GIS要提供四个方面的能力:• 提供二维和三维一体化的基础底图和统一坐标系统的能力;• 提供各个BIM单体之间连接网络管...

Mybatis之联表查询(多对多)_Ich will mit dir S wim的博客-程序员信息网_多对多联表查询

使用 &lt;resultMap&gt;标签以及&lt;association&gt;和&lt;collection&gt;子标签,进行关联查询.Pojo里面的User类public class User implements Serializable { private Integer id; private String username; private String address; private Date birthday; private Strin

联想服务器AR系列,联想发布ThinkReality A6 AR眼镜:搭载骁龙845 电池4000mAh_weixin_39743622的博客-程序员信息网

在推出了ThinkBook系列和新款ThinkPad X1隐士后,联想还为那些企业级客户准备了ThinkReality系列产品。其中该系列的首款产品便是A6 AR眼镜,它能简化企业AR解决方案的部署,并能与其他团队成员进行远程协作。ThinkReality A6 AR眼镜的整机重量为380g,前置两个鱼眼摄像头和一个IMU(测量传感器),并内置了高通骁龙845移动平台。与市面上其他的AR眼镜相比,...

Java 计算字符串表达式(字符串代码)_扣拉肖克钉的博客-程序员信息网_java字符串表达式计算

Java 计算字符串表达式(字符串代码)Java 执行字符串代码的方案有很多中,一般情况下我们计算字符串表达式的场景有:计算逻辑判断式,并返回判断结果(true,false)计算表达式值,一般返回结果为数值根据条件简单拼接字符串,返回结果为拼接文本我们可以使用 Java 内部自带的 JavaScript 引擎实现上述效果。import javax.script.ScriptEngine;import javax.script.ScriptEngineManager;import java

jsp创建excel文件 ,并指定下载路径_轻松qinsong的博客-程序员信息网

//下载excel文件 @RequestMapping(value="loadExcel.do",method=RequestMethod.GET) public void loadTxt(HttpServletRequest request,HttpServletResponse response){ List xls = new ArrayList(); Domai

推荐文章

热门文章

相关标签