加载中…
个人资料
fox1987
fox1987
  • 博客等级:
  • 博客积分:0
  • 博客访问:1,416
  • 关注人气:12
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
博文
标签:

最大流

最小割

教育

file:///C:/DOCUME%7E1/fox1987/LOCALS%7E1/Temp/moz-screenshot-2.png从源点开始,找到一个仍有剩余能力的路径,标注剩余能力,剩余能力标注为当前的剩余能力和前一跳剩余能力的较小值,直到标注到汇点。每次寻找下一跳结点按照编号从小到大的顺序如下图所示:源点是VS ,汇点是VT。从VS开始,VS到V1的路径没有剩余能力了(5,5)(容量为5,流量也为5,满了),所以看VS到V2的路径(4,2),剩余能力为2(4-2)。所以当前的剩余能力为2,在v2处标记为【vs,2】,表示从vs流入,剩余能力为2,然后看v2到v5,当前剩余能力为3,上一结点v2的剩余能力为2,所以v5处标记为【v2,2】。看v5到v1由于是v1流向v5的,所以标记为【-v5,2】(方向是负的,所以剩余能力直接取上一跳剩余能力即可),然后v1到v4的,剩余能力为3,所以v4处
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有