小结:二分图匹配

时间:2023-02-12 06:14:45

概要:

可以用匈牙利或者网络流(听说Dinic是O(sqrt(V)*E),isap我不知道,大概一样吧。)

应用:

最大匹配、最小点覆盖、最大独立集、最小路径覆盖、二分图完美匹配等。

技巧及注意:

匈牙利是O(nm)的,比网络流慢。

KM比网络流慢。

(还是写网络流吧。。。)

一些知识:二分图

在X集和Y集元素不同时,又要求哪些X集中元素有且只有一个Y集中的元素与之匹配时,可以先跑二分图匹配,然后依次删边,看是否还能继续匹配,如果不能就是一个答案。例如:

  1. 【wikioi】1222 信与信封问题(二分图+特殊的技巧)

棋盘上黑白染色:如果题目意思能够使得在棋盘中可以黑白染色(即一类和另一类不交),那么我们可以考虑二分图匹配

  1. 【vijos】1729 Knights(匈牙利)
  2. 【BZOJ】1059: [ZJOI2007]矩阵游戏(二分图匹配)