网络流与匹配小记

OI

二分图

二分图最大匹配

• 每次不断寻找交错路来增广，无法增广时一定是最大匹配（对于一般图也成立）

• 一个二分图中的最大匹配数等于这个图中的最小点覆盖数

• 最大独立集与最小点覆盖互补（适用于一般图）

• 最小路径覆盖（拆点）

匈牙利算法

• 交错路的模型可以结合博弈，有经典的二分图博弈

• 由于不断增广是对的，所以可以结合搜索来找到字典序最小/任意k个解

• 假设 $n$ 远大于 $m$，时间复杂度可以做到 $O(nm+m^3)$，在 $n,m$ 大小不平衡时很有用。

• 似乎还有个叫做匈牙利树

Hall定理

• 可以结合集合幂级数，或者状压。还有利用一些别的性质。

一般图

Dilworth定理

最小链覆盖（使链最少）= 最长反链长度 = 偏序集宽度

最小反链覆盖=最长链长度=偏序集深度