SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1189][HNOI2007]紧急疏散evacuate(二分答案 + 最大流)

做了好几题裸的最大流,来一道稍微不裸一点的(不过这种经典题也没什么好说的),首先题目二分答案,然后用最大流验证是否满流。首先要做一次BFS预处理,预处理出所有的空点到所有门的最短路。做最大流时,首先将源点向所有空位置连一条容量为1的边,将所有的门向汇点连一条容量为时间的边(一开始连了N * M的容量,坑了好久。。),再将所有空点向时间内能到达的门连一条容量为1的边。     Read more