题目链接 大致题意 给出一个费用流图，每条边的流量上限相同且不固定。有$q$个询问，每个询问中给出每条边的流量上限（分数，且保证$\leq 1$）。当图中的流量为 $1$ 个单位的时候，求出此时的费用。 分析 首先是询问个数，有$1e5$次询问，则需要预处理整个图，然后O(1)作答才可以过。然后注意到题目中给出的数据规模，图的边数只有$100$条 首先由于边的流量均为分数（$\frac{u}{v}…
题目链接 大致题意 给出一个费用流图，每条边的流量上限相同且不固定。有$q$个询问，每个询问中给出每条边的流量上限（分数，且保证$\leq 1$）。当图中的流量为 $1$ 个单位的时候，求出此时的费用。 分析 首先是询问个数，有$1e5$次询问，则需要预处理整个图，然后O(1)作答才可以过。然后注意到题目中给出的数据规模，图的边数只有$100$条 首先由于边的流量均为分数（$\frac{u}{v}…
讨论
登录后参与讨论
还没有评论，来说第一句吧。