注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1189][HNOI2007]紧急疏散evacuate  

2014-10-22 22:15:51|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1189: [HNOI2007]紧急疏散evacuate

首先说一下BZOJ上题目没说清的地方,如果无解要输出impossible
神题……死也没想出来。
然后请教了一下zky神犇终于会了Orz

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 20+10;
const int P = N*N;
const int M = P*P*2;
const int MAX = 1E9+10;
int n,m,T,start,end,large,ans,level[P];
int data[N][2],all[2];
short map[N][N];
const int S[5][2] = {{},{0,-1},{0,1},{-1,0},{1,0}};
int scan(){int i=0;scanf("%d",&i);return i;}
struct Po{int x,y;Po(int a,int b):x(a),y(b){}};
struct Point{
Point(){next = NULL;}
int d;Point *next;
void push(int);
}point[P],*cur[P];
queue<Point*>pupa;
Point *newPoint(){
if(pupa.empty())return new Point();
Point *r = pupa.front();pupa.pop();
if(r->next)pupa.push(r->next);
*r = Point();return r;
}
void Point::push(int a){
Point *l = newPoint();
l->next = next;next = l;
l->d = a;
}
struct Edge{
int from,to,cap,flow;
Edge(){}
Edge(int f,int t,int c,int fl):from(f),to(t),cap(c),flow(fl){}
}edges[M];
void AddEdge(int from,int to,int flow){
point[from].push(T);
edges[T++] = Edge(from,to,flow,0);
point[to].push(T);
edges[T++] = Edge(to,from,0,0);
}
queue<int>dui;
int calc(int i,int j){return (i-1)*m+j;}
bool bfs(){
for(int i=1;i<=large;i++)level[i] = 0;
level[start] = 1;
dui.push(start);
while(!dui.empty()){
int now = dui.front();dui.pop();
for(Point *i = point[now].next;i!=NULL;i=i->next){
Edge e = edges[i->d];
if(!level[e.to] && e.cap > e.flow){
level[e.to] = level[now] + 1;
dui.push(e.to);
}
}
}return level[end]!=0;
}
int dfs(int now,int a){
if(now == end|| !a)return a;
int flow=0,l;
for(Point *&i = cur[now];i!=NULL;i=i->next){
Edge &e = edges[i->d];
if(level[e.to] == level[now]+1 && (l = dfs(e.to,min(a,e.cap - e.flow)))){
flow += l;
e.flow += l;
edges[i->d^1].flow -= l;
a -= l;
if(!a)break;
}
}return flow;
}
int dinic(){
int flow=0;
while(bfs()){
for(int i=1;i<=large;i++)cur[i] = point[i].next;
int flag;
while((flag = dfs(start,MAX)))
flow += flag;
}return flow;
}
int dis[N][N],ti[N][N],TT;
queue<Po>q;
bool check(int mid){
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(!map[i][j])AddEdge(start,calc(i,j),1);
for(i=1;i<=all[1];i++){//each door
TT++;
int door = calc(data[i][0],data[i][1]);
AddEdge(door,end,mid);
//people
q.push(Po(data[i][0],data[i][1]));
while(!q.empty()){
Po now = q.front();q.pop();
if(dis[now.x][now.y] == mid)continue;
for(k=1;k<=4;k++){
int x,y;
x = now.x + S[k][0];y = now.y + S[k][1];
if(map[x][y])continue;
if(ti[x][y] != TT){
ti[x][y] = TT;
dis[x][y] = dis[now.x][now.y]+1;
AddEdge(calc(x,y),door,MAX);
q.push(Po(x,y));
}
}
}
}
j = dinic();
return j == all[0];
}
int main(){
freopen("in.txt","r",stdin);
int i,j,k;char cc;
n = scan();m = scan();
start = calc(n,m)+1;
large = end = start + 1;
/*
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
printf("%d ",calc(i,j));
printf("\n");
}*/
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
map[i][j] = -1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);
if(cc=='X')map[i][j] = 1;
if(cc=='D'){
all[1]++;
map[i][j] = 2;
data[all[1]][0] = i;
data[all[1]][1] = j;
}
if(cc=='.')map[i][j] = 0,all[0]++;
}
if(!all[0]){printf("0\n");return 0;}
int l,r;
l = 1;r = n*m*2+1;
check(5);
while(l < r){
int mid = (l+r)/2;
if(check(mid))r = mid;
else l = mid+1;
for(i=1;i<=large;i++) if(point[i].next)pupa.push(point[i].next),point[i].next = NULL;
}
if(l == n*m*2+1)printf("impossible\n");
else printf("%d\n",l);
return 0;
}

题解:
二分答案+网络流检查
每次二分一个答案mid
检查的时候每次从每个门在mid时间内能走到的点向那个门连一条边,容量为max
然后源点向每个空格子连1
每个门向汇点连mid边
如果最大流 = 空格子数就可行。
-------------------------------------------------
另:
遇到一件奇葩的事情……
做完题习惯性去看了一下Ranklist
1189: [HNOI2007]紧急疏散evacuate - 时光机 - 时光机TimeMachine
 
 我的名字变成了一个叫nilihan1999的神犇23333
最厉害的是zky说他认识这个人……而且好像就是HN的,难道说我做了一道HN神题然后穿越到HN去了?
-------------------------------------------------
  评论这张
 
阅读(76)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017