BZOJ 1189 紧急疏散evacuate 二分+BFS+最大流

2024-06-15 11:08

文章标签 二分 bfs 最大 bzoj evacuate 紧急疏散 1189

本文主要是介绍BZOJ 1189 紧急疏散evacuate 二分+BFS+最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

建图的时候需要拆点，按照每一个时间点拆点，主要可以保证每次只有一个人走出门。BFS处理出人到门的距离二分答案，判断是否可以建边，S指向每一块空地，空地到门如果可以建边就建一条容量为x的边每个门按照时间拆点，保证单位时间内走一次，然后跑最大流

这篇关于BZOJ 1189 紧急疏散evacuate 二分+BFS+最大流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/1063277。 23002807@qq.com

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了题意：已知圆台的体积，求高度首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj 3723 kruscal，反边取最大生成树。

题意：需要征募女兵N人，男兵M人。每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。要求通过适当的招募顺序使得征募所有人的费用最小。解析：先设想无向图，在征募某个人a时，如果使用了a和b之间的关系

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976：题意：在n场考试中，每场考试共有b题，答对的题目有a题。允许去掉k场考试，求能达到的最高正确率是多少。解析：假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。然后二分x就行了。代码： #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意： n件湿度为num的衣服，每秒钟自己可以蒸发掉1个湿度。然而如果使用了暖炉，每秒可以烧掉k个湿度，但不计算蒸发了。现在问这么多的衣服，怎么烧事件最短。解析：二分答案咯。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意：有一些石头排成一条线，第一个和最后一个不能去掉。其余的共可以去掉m块，要使去掉后石头间距的最小值最大。解析：二分石头，最小值最大。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意：一条街上有n个大楼，坐标为xi，yi，bi个人在里面工作。然后防空洞的坐标为pj，qj，可以容纳cj个人。从大楼i中的人到防空洞j去避难所需的时间为 abs（xi - pi） + （yi - qi） + 1。现在设计了一个避难计划，指定从大楼i到防空洞j避难的人数 eij。判断如果按照原计划进行，所有人避难所用的时间总和是不是最小的。若是，输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意：农场里有n块地，其中约翰的家在1号地，二n号地有个很大的仓库。农场有M条道路（双向），道路i连接着ai号地和bi号地，长度为ci。约翰希望按照从家里出发，经过若干块地后到达仓库，然后再返回家中的顺序带朋友参观。如果要求往返不能经过同一条路两次，求参观路线总长度的最小值。解析：如果只考虑去或者回的情况，问题只不过是无向图中两点之间的最短路问题。但是现在要去要回

poj 2594 二分图最大独立集

题意：求一张图的最大独立集，这题不同的地方在于，间接相邻的点也可以有一条边，所以用floyd来把间接相邻的边也连起来。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

BZOJ 1189 紧急疏散evacuate 二分+BFS+最大流

相关文章