算法-笔记3

flow network

The quantity f (e) is called the flow of edge e.

flow

1. 除了s和t，所有的节点进入等于出去，比如 v3： 1+2+1 = 2 + 2
2. [f]=10的意思就是s发出了10，t接受了10。

maximum flow

这种使用flow network 更加有效率。

cut

Ford-Fulkerson algorithm

求解maximum flow的方法。采用了贪婪。但只采用贪婪得不到最优解，会在图右边堵住。

• 优化方法：把边（无论满没满）往两侧推，推到那些有空余的边上。也就是： 可以在有剩余容量的边上正向增加，并在已经承载了流量的边上反向增加，以将其分流到不同的方向。

Maximum Bipartite Matching

一个两个集合一一对应的图。