最小费用最大流算法:最小费用最大流的例题[朗读]

可以采用对偶法以费用c为权通过福德算法先找从起点至终点的最短路,再以该最短路为增广链调整流量,每一次调整都以矩阵a记录调整的结果.为了能够满足增广链上正向弧非饱合、逆向弧非零流的条件,在每一次以c为权寻找最短路之前,对费用c矩阵进行调整.将正向饱合弧、逆向零流弧对应的c值设为无穷大,非饱合弧的c值设为初始值,这样一来,计算出的最短路径增广链就不会包括正向饱合弧与逆向零流弧了。