本文主要是介绍bzoj1189: [HNOI2007]紧急疏散evacuate，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1189
思路：一种简单的网络流建图：
预处理两点间距离
从S向每个空地连1的边，每个空地向它在二分的时间内能到的出口连边，出口在向汇连T的边
这也是很多题解的做法
但这是错的...
当很多人距离门很远时，他们就可能在时间快到时堆在门口出不去，这种建图就忽略了这一点
所以我们要拆点
还是二分最大时间T，从S向每个空地连1的边
把每个门拆成T个点，表示每个时间，由每个点向汇连容量为1的边，表示每个时间只能出去一个人
然后由时间早的点向后一个时间的点连边，表示可以在门口等待到下一个时间出去
每个空地向它最早到达这个门的时间所代表的点连1的边
判断最大流是否等于空地数即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const int maxn=40010,maxm=1000010,inf=(int)1e9;
using namespace std;
int n,m,dis[510][510],map[25][25],dor[510],dcnt,blk[510],bcnt,head,tail;char ch[25][25];bool bo[25][25];
int pre[maxm],now[maxn],son[maxm],val[maxm],tot,di[maxn],S=maxn-2,T=maxn-1,maxt=80;
struct poi{int x,y;}q[510];
int id(int x,int y){return (x-1)*m+y;}void bfs(int sx,int sy){int st=id(sx,sy);memset(dis[st],63,sizeof(dis[st]));memset(bo,0,sizeof(bo));q[tail=1]=(poi){sx,sy};head=0,dis[st][st]=0,bo[sx][sy]=1;while (head!=tail){if (++head>500) head=1;poi a=q[head];for (int i=0;i<4;i++){int nx=a.x+dx[i],ny=a.y+dy[i];if (bo[nx][ny]) continue;if (map[nx][ny]==1){if (++tail>500) tail=1;bo[nx][ny]=1,dis[st][id(nx,ny)]=dis[st][id(a.x,a.y)]+1;q[tail]=(poi){nx,ny};}else if (map[nx][ny]==2)bo[nx][ny]=1,dis[st][id(nx,ny)]=dis[st][id(a.x,a.y)]+1;}}
}void init(){for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (map[i][j]==1) bfs(i,j),blk[++bcnt]=id(i,j);else if (map[i][j]==2) dor[++dcnt]=id(i,j);
}
struct Tflow{int q[maxn+10],head,tail;int id(int x,int tim){return (x-1)*maxt+tim+bcnt;}void add(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}void ins(int a,int b,int c){add(a,b,c),add(b,a,0);}void clear(){memset(now,0,sizeof(now)),tot=1;}bool bfs(){memset(di,-1,sizeof(di));q[1]=S,di[S]=0,head=0,tail=1;while (head!=tail){if (++head>maxm) head=1;int x=q[head];for (int y=now[x];y;y=pre[y])if (di[son[y]]==-1&&val[y]){if (++tail>maxm) tail=1;di[son[y]]=di[x]+1,q[tail]=son[y];}}return di[T]>0;}int find(int x,int low){if (x==T) return low;int y,res=0;for (y=now[x];y;y=pre[y]){if (!val[y]||di[son[y]]!=di[x]+1) continue;int tmp=find(son[y],min(low,val[y]));val[y]-=tmp,val[y^1]+=tmp,res+=tmp,low-=tmp;if (!low) break;}if (!y) di[x]=-1;return res;}bool dinic(int lim){int res=0;clear();for (int i=1;i<=bcnt;i++) ins(S,i,1);for (int i=1;i<=dcnt;i++) for (int j=1;j<=lim;j++){ins(id(i,j),T,1);if (j>1) ins(id(i,j-1),id(i,j),inf);}for (int i=1;i<=bcnt;i++)for (int j=1;j<=dcnt;j++){int x=blk[i],y=dor[j];if (dis[x][y]<=lim) ins(i,id(j,dis[x][y]),1);}while (bfs()) res+=find(S,inf);return res==bcnt;}
}Ts;void work(){int l=1,r=n*m,mid=(l+r)>>1,ans=-1;while (l<=r){if (Ts.dinic(mid)) r=mid-1,ans=mid;else l=mid+1;mid=(l+r)>>1;}if (ans==-1) puts("impossible");else printf("%d\n",ans);
}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",ch[i]+1);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (ch[i][j]=='D') map[i][j]=2;else if (ch[i][j]=='.') map[i][j]=1;init(),work();return 0;
}这篇关于bzoj1189: [HNOI2007]紧急疏散evacuate的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
