SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

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

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

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1433][ZJOI2009]假期的宿舍(最大流)

又是一道最大流,建图很简单,源点到所有的在校学生和外校学生建一条容量为1的边,所有在校学生的床(感觉听起来怪怪的)到汇点连一条边,所有在校学生和自己的床连一条边,所有学生到他认识的在校学生的床连一条边。然后做最大流与需要住校的学生总数比较,相等就输出^_^,不相等就输出T_T(这个太逗了)。。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1066][SCOI2007]蜥蜴(最大流)

这道题就是最大流,首先对柱子进行拆点,一个入点和一个出点,入点向出点连一条容量为柱子高度的边,从每个柱子的出点,向可以一次跳到的所有柱子的入点连一条容量为当前柱子高度的边,再从每个可以一次跳出的柱子向汇点连一条容量为柱子高度的边,从源点向每个有蜥蜴的柱子的入点连一条容量为1的边,然后做一次最大流即可。当然答案输出的是不能跳出的蜥蜴,我被坑了好久233     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1934][SHOI2007]Vote 善意的投票(最大流)

双倍经验题,详见     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ2768][JLOI2010]冠军调查(最大流 最高标号预流推进 + GAP优化)

这题很显然是一道最小割的题目,然后题目只要求最小割的容量,那么直接跑个最大流(关于最小割-最大流定理请自行谷歌),以前写过DINIC感觉不够高大上,然后果断来一个最高标号预流推进秀优越,事实上这个时间复杂度的确很优秀。一开始我写的没加GAP优化,400+ms,跑得比DINIC还慢,真是不爽,下午看到了一种叫GAP优化的东西,加上之后就28ms了,怒刷到rank2。     Read more