AC第一道网络最大流

写于2007-06-09 23:51

最近没心情学习，也不大想编程了，整天就开着电脑，上QQ也不知和谁聊，上校内也是随便逛逛，昨天才开始看的网络流，定理一大堆，很多都看不大懂。

早上起来就拿起算法导论来研究网络流，看了一下Ford-Fulkerson算法，会做一点最大流，虽然不大明白为什么要这么做。

Ford-Fulkerson算法：

基本思路是找增广路径，根据最大流最小割定理直到找不到增广路径则找到了最大流。

找到增广路径上找出流量最小的值，路径上每条边正向的流减去该值，反向的流加上该值。

找增广路径可以用广搜也可以用深搜，用Dijkstra找最短路径也是可以的。