网络流算法和并查集算法

帮忙阐述下网络流算法和并查集

NOIP会考到吗？

====================================================

网络流(network flows)

1。 网络流先要构图 通常是一道题目最难的地方。（有的时候需要增加一个源点和一个汇点）

2。 然后就是不断找有没有可改进路 如果有则改进。

3。 当找到一条改进路时 需要找这条路的瓶颈 也就是最多能通过多少流。

4。 最后更新这一条路。返回2。接着找。直到找不到路则是最大流。

网络流还有费用流等变形。也可以解决二分图等问题。

理解的难点是返向流。

=======================================================

并查集(MFS)

一些问题有时需要根据给定的等价关系（自反性、对称性、传递性）将不同元素进行划分。把具有等价关系的元素集合起来。

划分方法

先让每个元素各自为阵 然后依照等价关系分析每个元素 进行归并。

实现的方法之一 每个集合用一棵树表示。树上任意两结点之间有等价关系。

我们还可以进行 小树并到大树、压缩找路径等方式来改进。

=======================================================================

并查集可能在提高组中考。网络流按道理不会的。

如果是普及组的话是不会考这两样的。

            —— 陌亲笔。