首页 > 代码库 > BZOJ 1189 HNOI2007 紧急疏散evacuate 二分答案+最大流
BZOJ 1189 HNOI2007 紧急疏散evacuate 二分答案+最大流
题目大意:给定一个m*n的地图,每个点有可能是空地、墙或者出口,每个空地初始站着一个人,每一时刻可以向周围走1格,门每一时刻只能通过一个人,求最短多少时间后所有人可以撤离
首先从每个出口出发开始广搜,得到每个空地到所有出口的距离
然后二分答案,每次建图如下:
从源点向每个空地一条流量为1的边
如果一个空地能在规定时间到达某个出口,就从这个空地出发向该出口链接一条流量为1的边
每个出口向汇点连接一条流量为时间的边
然后跑最大流验证即可 注意图有不连通的情况 所以广搜要清初值(这个没人会忘吧QAQ 但是我卡了一晚上……)
那么问题来了:
会不会有这样的情况,规定时间为2,而两个人同时在时间2到达门口,于是堵住了,但是跑出来的的答案却是2呢?
……很不幸地告诉你 会
比如说这组样例:
这个样例的答案是3 但是这样建图跑出来是2
这幅图中间下方的人有两个选择:从上面逃生或从下面逃生
如果从下面逃生 那么左右两个人到上面的距离都是3 2时间内无法逃出
如果从上面逃生 那么两侧的人就会同时在时间2到达下侧出口 于是就愉快地卡住了~~
无视吧。。。不考虑这个这题还是能做的。。。。。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 30 #define S abcd(0,0) #define T abcd(29,29) #define INF 0x3f3f3f3f using namespace std; typedef pair<int,int> abcd; template<typename Temp>class Reader{ private: Temp xx[M][M]; public: Temp& operator [] (abcd x) { return xx[x.first][x.second]; } Temp* operator [] (int x) { return xx[x]; } inline void Clear(int x) { memset(xx,x,sizeof xx); } }; struct edge{ abcd to; int f,next; }table[100100]; Reader<int>head;int tot=1; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; int m,n,cnt,per; char s[M]; abcd exi[M<<2]; Reader<int>f[M<<2]; Reader<int>map; Reader<int>dpt; void Add(abcd x,abcd y,int z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } void Link(abcd x,abcd y,int z) { Add(x,y,z); Add(y,x,0); } void BFS(abcd start,Reader<int>&f) { static abcd q[1<<16]; int i,r=0,h=0; f.Clear(0x3f);q[++r]=start;f[start]=0; while(r!=h) { abcd x=q[++h]; for(i=0;i<4;i++) { abcd y(x.first+dx[i],x.second+dy[i]); if(y.first<=0||y.second<=0||y.first>m||y.second>n) continue; if(map[y]||f[y]!=0x3f3f3f3f) continue; f[y]=f[x]+1; q[++r]=y; } } } bool BFS() { static abcd q[1<<16]; int i,r=0,h=0; dpt.Clear(-1); q[++r]=S;dpt[S]=1; while(r!=h) { abcd x=q[++h]; for(i=head[x];i;i=table[i].next) if(table[i].f&&!~dpt[table[i].to]) { dpt[table[i].to]=dpt[x]+1; q[++r]=table[i].to; if(table[i].to==T) return true; } } return false; } int Dinic(abcd x,int flow) { int i,left=flow; if(x==T) return flow; for(i=head[x];i&&left;i=table[i].next) if(table[i].f&&dpt[table[i].to]==dpt[x]+1) { int temp=Dinic(table[i].to,min(left,table[i].f) ); if(!temp) dpt[table[i].to]=-1; left-=temp; table[i].f-=temp; table[i^1].f+=temp; } return flow-left; } bool Judge(int x) { int i,j,k,re=0; head.Clear(0),tot=1; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(map[i][j]==0) { Link(S,abcd(i,j),1); for(k=1;k<=cnt;k++) if(f[k][i][j]<=x) Link(abcd(i,j),exi[k],1); } for(k=1;k<=cnt;k++) Link(exi[k],T,x); while( BFS() ) re+=Dinic(S,INF); return re==per; } int Bisection() { int l=0,r=m*n; while(l+1<r) { int mid=l+r>>1; if( Judge(mid) ) r=mid; else l=mid; } if( Judge(l) ) return l; return r; } int main() { //freopen("evacuate.in","r",stdin); //freopen("evacuate.out","w",stdout); int i,j; cin>>m>>n; for(i=1;i<=m;i++) { scanf("%s",s+1); for(j=1;j<=n;j++) switch(s[j]) { case 'D': exi[++cnt]=abcd(i,j); case 'X': map[i][j]=1; break; case '.': map[i][j]=0; ++per; break; } } for(i=1;i<=cnt;i++) BFS(exi[i],f[i]); int ans=Bisection(); if(ans==m*n) puts("impossible"); else cout<<ans<<endl; return 0; }
BZOJ 1189 HNOI2007 紧急疏散evacuate 二分答案+最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。