题目链接 大致题意 给出一个费用流图，每条边的流量上限相同且不固定。有个询问，每个询问中给出每条边的流量上限（分数，且保证）。当图中的流量为 个单位的时候，求出此时的费用。 分析 首先是询问个数，有次询问，则需要预处理整个图，然后O(1)作答才可以过然后注意到题目中给出的数据规模，图的边数只有条 首先由于边的流量均为分数（），而总流量为 个单位。我们先扩大倍，将每条边的流量固定为 个单位，此时流量为 个单位 考虑在最大流使用 SPFA 查找路径时，当查找到一条路径时，此路径的流量一定为 （根据上述的设定）。由于采用的本身便是最短路查找路径，得到的路径的费用为当前网络图下的最低费用。 所以可以稍...