icontofig | 发布于 2019-07-13 19:09:19 | 阅读量 297 | 最短路 二分 离散化 网络流 最大流
发布于 2019-07-13 19:09:19 | 最短路 二分 离散化 网络流 最大流
BAPC18 I In Case of an Invasion,Please... 最短路+离散化+二分+最大流
题目大意有n个居民点,m条双向有权路径,和s个避难所。每个居民点有pi个居民,每个避难所的容量为Ci。 现在求能够让所有人避难的最少的需要的时间。 题解我们如果有一个时间,那么我们该如何判断在这个时间内能不能安置所有居民呢? 很简单就能想到,这是一个利用最大流判断是否存在可行流的问题。 建立从源点s到每个居民点的容量为pi的有向边,从每个居民点到每个避难所容量为+∞的有向边,从每个避难所到汇点t容量为ci的有向边。然后建完图直接跑最大流,判断最大流的流量是否等于所有的居民人数总和即可。 那这个时间我们该如何去求? 答案是可以二分。 二分出一个答案时间,然后检验这个时间下能否将所有人安置好。当然
继续阅读