05数学(算法)与经济管理

03-网络与最大流量2

2021-08-10 79 1

简介 求得所有路径流量和

在军事演习中,张司令希望将部队尽快从 A 地通过公路网(见下图)运送到 F 地

图中标出了各路段上的最大运量(单位:千人/小时)。根据该图可以算出,从A地到F地的最大运量是()千人/小时。

upfile


解析:


    在本章节的上一篇文章中,详细介绍了最大流量的解题方法。不断抽取路径上的"短板",直到路径"不通"为止。


    注意,抽取的时候先抽取某条路径上的最大“短板”


    1. 抽取ABF路径上的短板8

upfile


    抽取短板8之后

upfile


    2. 抽取路径ABEF上的短板4

    upfile



    抽取后

upfile


    3. 抽取ADEF上的4

upfile


抽取后

upfile


    4. 抽取ADECF上的3

upfile


    抽取后

upfile


    5. 抽取ACEF上的2

upfile

    抽取后

upfile


    6.抽取ABCDF上的1

    upfile

    抽取后, A到F已经不存在可以走通的路径。

upfile




    最终结果:

    8 + 4 + 4 + 3 + 2 + 1 = 22







点赞 1

文章评论

欢迎您:

纸上得来终觉浅,绝知此事要躬行!

112 文章 38820 浏览 3 评论

联系我

  •   QQ:    361352119
  •  Email:  lisimmy@sina.com
  • 微信: