第8节-最小费用流资料课件

第8节最小费用最大流13,613,6实际问题实例：一个工厂要将产品送到火车站，可以有许多道路供其选择，在不同路线上每吨货物的运费并不相同，而且每条路线只能有限重量的货物运输，那么要将w吨的产品从工厂送到火车站，用什么方法可以使运费最少？v0v3v5v2v1v4vn(3,3,0)(4,6,0)(4,3,0)(3,4,0)(2,5,0)(9,3,0)(2,3,0)(2,2,0)(1,1,0)(2,2,0)(单位运费，边容量，流值）v0v3v5v2v1v4vn(3,3,0)(4,6,0)(4,3,0)(3,4,0)(2,5,0)(9,3,0)(2,3,0)(2,2,0)(1,1,0)(2,2,0)将各弧的单位运费作为长度，求v0到vn的最短增流路v0v1v3v4vn，路长为8，可增加1单位的流值。v0v3v5v2v1v4vn(3,3,0)(4,6,0)(4,3,0)(3,4,0)(2,5,0)(9,3,0)(2,3,0)(2,2,0)(1,1,0)(2,2,0)将各弧的单位运费作为长度，求v0到vn的最短增流路v0v1v3v4vn，路长为8，可增加1单位的流值。v0v3v5v2v1v4vn(3,3,0)(4,6,0)(4,3,0)(3,4,0)(2,5,0)(9,3,0)(2,3,0)(2,2,0)(1,1,0)(2,2,0)将各弧的单位运费作为长度，求v0到vn的最短增流路v0v1v3v4vn，路长为8，可增加1单位的流值。v0v3v5v2v1v4vn(3,3,0)(4,6,0)(4,3,0)(3,4,0)(2,5,0)(9,3,0)(2,3,0)(2,2,0)(1,1,0)(2,2,0)将各弧的单位运费作为长度，求v0到vn的最短增流路v0v1v3v4vn，路长为8，可增加1单位的流值。v0v3v5v2v1v4vn(3,3,1)(4,6,0)(4,3,0)(3,4,0)(2,5,1)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)将各弧的单位运费作为长度，求v0到vn的最短增流路v0v1v3v4vn，路长为8，可增加1单位的流值。v0v3v5v2v1v4vn(3,3,1)(4,6,0)(4,3,0)(3,4,0)(2,5,1)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)再求v0到vn的最短增流路v0v1v4vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,1)(4,6,0)(4,3,0)(3,4,0)(2,5,1)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)再求v0到vn的最短增流路v0v1v4vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,1)(4,6,0)(4,3,0)(3,4,0)(2,5,1)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)再求v0到vn的最短增流路v0v1v4vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,0)(4,3,2)(3,4,0)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)再求v0到vn的最短增流路v0v1v4vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,0)(4,3,2)(3,4,0)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)再求v0到vn的最短增流路v0v2v5vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,0)(4,3,2)(3,4,0)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)再求v0到vn的最短增流路v0v2v5vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,0)(4,3,2)(3,4,0)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,0)再求v0到vn的最短增流路v0v2v5vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,2)(4,3,2)(3,4,2)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v5vn，路长为9，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,2)(4,3,2)(3,4,2)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v1v4vn，路长为14，可增加1单位的流值。（v3v1反向弧，同最大流处理）v0v3v5v2v1v4vn(3,3,3)(4,6,2)(4,3,2)(3,4,2)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v1v4vn，路长为14，可增加1单位的流值。（v3v1反向弧，同最大流处理）v0v3v5v2v1v4vn(3,3,3)(4,6,2)(4,3,2)(3,4,2)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v1v4vn，路长为14，可增加1单位的流值。（v3v1反向弧，同最大流处理）v0v3v5v2v1v4vn(3,3,3)(4,6,2)(4,3,2)(3,4,2)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v1v4vn，路长为14，可增加1单位的流值。（v3v1反向弧，同最大流处理）v0v3v5v2v1v4vn(3,3,3)(4,6,2)(4,3,2)(3,4,2)(2,5,3)(9,3,0)(2,3,0)(2,2,1)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v1v4vn，路长为14，可增加1单位的流值。（v3v1反向弧，同最大流处理）v0v3v5v2v1v4vn(3,3,3)(4,6,3)(4,3,3)(3,4,2)(2,5,4)(9,3,0)(2,3,1)(2,2,0)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v1v4vn，路长为14，可增加1单位的流值。（v3v1反向弧，同最大流处理）v0v3v5v2v1v4vn(3,3,3)(4,6,3)(4,3,3)(3,4,2)(2,5,4)(9,3,0)(2,3,1)(2,2,0)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v5vn，路长为18，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,3)(4,3,3)(3,4,2)(2,5,4)(9,3,0)(2,3,1)(2,2,0)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v5vn，路长为18，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,3)(4,3,3)(3,4,2)(2,5,4)(9,3,0)(2,3,1)(2,2,0)(1,1,1)(2,2,2)再求v0到vn的最短增流路v0v2v3v5vn，路长为18，可增加2单位的流值。v0v3v5v2v1v4vn(3,3,3)(4,6,3)(4,3,3)(3,4,2)(2,5,4)(9,3,0)(2,3,1)(2,2,0)(1,1,1)(2,2,2)再求v0