[bzoj3130]:[Sdoi2013]费用流

Description

对于一张给定的运输网络,Alice先确定一个最大流,如果有多种解,Alice可以任选一种;之后Bob在每条边上分配单位花费(单位花费必须是非负实数),要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到,Bob在分配单位花费之前,已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小,而Bob希望总费用尽量大。我们想知道,如果两个人都执行最优策略,最大流的值和总费用分别为多少。


阅读更多