网络流算法

网络流算法 网络流算法用于解决从源点到汇点最大流的问题。 Edmonds-Karp算法 算法主要思想： 每次BFS找到一条从源点到汇点的最少路径数的可行路径，同时把这条路径塞满，这条路上的最小容量即为这条路径的流量。然后将这条路径的正向边删除，增加一条容量相同的反向边，当BFS无法进行下去的时候，则算法结束，最大流为每次BFS找到的可行路径的流量和。

Poj1273 Drainage Ditches

2.Dinic算法
?
为了少做几次bfs。
?
解决方法：先对结点进行分层，然后以层次数进行dfs，这样一次的增广过程可以通过dfs找到几条可行路径。结点回溯回溯到该路径的流量对应的最小层数容量边的起点。同时还要注意要将原图备份，使用原图上的边的容量减去做完最大流的残余网络上的边的剩余容量，就是边的容量。
?
POJ 3436 ACM Computer Factory
?
?
? 
其他典型例题：
?
poj2112 Optimal Milking
?
Poj1149 pigs
?
?
?
?
?
3. 有流量下界的网络最大流处理方法：
?
思路：分离下界
?
添加新的节点X，Y，使得X，Y成为新图的源点和汇点，若新图的最大流中，源点Y的所有发出边全部被覆盖，则原图有解，否则无解。这样就转换成了普通网络流问题进行解决。
?
POj2396 Budget
?
?
?
?
?
?
4.最小费用最大流
?
每条边上多了一个输送单位流量的费用参数,在最大流中寻找一个费用最小的最大流.
?
POJ 2135
?