高度由习惯堆积

分类 算法:网络流 下的文章

August 14, 2019

ZJOI2011 营救皮卡丘

题目题目链接思路首先,看数据范围比较小,想到网络流。对于最短路的那部分,在走到$j$的时候,不能经过$>j$的点,所以在$Floyd$的时候我们加一层限制$K<=j$处理出最短路。然后考虑网络流建边。会发现有这么几个限制:从小的点走向大的点每个点都必须走到不得超过$K$条路径因为每一条路径一定都是从较小的点走向较大的点的,所以其实这是一个$DAG$。然后考虑如何在建图中体现这些性...