network flow
05月 6, 2008
add a comment
重看了一遍网络流。结果相当郁闷。
那个写书的人的C++简直属于没事找“抽”的一类。动不动就CLASS,而且类型的定义和程序代码相距甚远,导致我看代码时不断地翻到前面去找定义。
收获是总算可以自己写出简单的预留推进(preflow push)算法了。最高标号应该也没问题了。
大概内容
最大流 最小割 增广路算法 预留推进
上下界最大流 上下界最小流
最小费用最大流 消圈算法 增广路算法
上下界最小费用最大流
平面图构图 -> 最大流 = 最小割 = 最短路