HBC20361[SDOI2013]费用流题解 （最大流和最小费用最大流）

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识， 最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量， 一个合法的网络流方案必须满足： (1)每条边的实际流量都不超过其最大流量且非负； (2)除了源点S和汇点T之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而S点的净流出流量等于T点的

Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。 最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量。 一个合法的网络流方案必须满足： (1)每条边的实际流量都不超过其最大流量且非负； (2)除了源点S和汇点T之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而S点的净流出流量等于T点的净流入流量，这个值也即该网络流方案的总运输量。 最大流问题就是对于给定的运输网络，求总运输量最大的网络流方案。 上图表示了一个最大流问题。对于每条边，右边的数代表该边的最大流量，左边的数代表在最优解中，该边的实际流量。需要注意到，一个最大流问题的解可能不是唯一的。 对于一张给定的运输网络，Alice先确定一个最大流，如果有多种解，Alice可以任选一种；之后Bob在每条边上分配单位花费（单位花费必须是非负实数），要求所有边的单位花费之和等于P。 总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到，Bob在分配单位花费之前，已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小，而Bob希望总费用尽量大。我们想知道，如果两个人都执行最优策略，最大流的值和总费用分别为多少。

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC20361[SDOI2013]费用流题解