/ Vijos / 讨论 / 分享 /

关于网络流 残留网络

初学网络流。。。 有点蒙了

残留网络 是由 剩余图 的前向边构成的

amber 在 最小割模型在信息学竞赛中的应用 中的概念介绍中说

1. f 是 G 的一个最大流

2. 残留网络Gf不含增广路径

这两条等价

但是 下面描述的这幅图

残余网络应该是 (s,1),(2,t) 两条边 所以没有增广路

但是事实上时有的啊。。。。请高手指点

点有四个 s,1,2,t

边有五条 以(a,b),f,c 描述每条边

s 1 1 2

s 2 2 2

1 t 2 2

2 1 1 1

2 t 1 2

不胜感激!

9 条评论

  • @ 2010-03-15 17:29:43

    ……

    orz楼上神牛

    对神牛来说

    什么书都可以拿来烤火

  • @ 2010-03-15 16:09:16

    不知我看的书如何

    算法艺术与信息学竞赛 刘汝佳 黄亮 著

    可以用来烤火用吗?

  • @ 2010-03-15 11:55:55

    所有LS LZ都神牛

  • @ 2010-03-10 22:12:15

    LS五色神牛

  • @ 2010-03-08 17:49:48

    .

    LZ神牛。

  • @ 2010-03-08 17:42:15

    我学dinic也看了那本书, 然后决定还是自己写……

  • @ 2010-03-07 20:40:27

    是f0的反向弧组成

    你那本书可以烧了来取暖,重新买本吧。。

  • @ 2010-03-07 13:42:23

    新编 实用算法分析与程序设计 王建德 吴永辉 编著

    第255页 引入残留网络Df 其中就有这么一段话。。。

  • @ 2010-03-06 21:41:45

    残留网络 是由 剩余图 的前向边构成的

    这句话你是听谁说的?

  • 1