二分图

图论

概念

二分图

若一个图 G=(V,E) 可以将定点分成两个点集 X,Y，使得同一个集合内的点之间没有边，则称 G 是一个二分图

匹配

若图 G 的一个边集 M 中任意两个边没有公共点，则称 M 是 G 的一个匹配，M 内的边数称为 M 的大小，大小最大的匹配称为 G 的最大匹配

独立集

若图 G 的一个点集 S 中任意两点之间没有边，则称 S 是 G 的一个独立集，S 内的点数称为 S 的大小，大小最大的独立集称为 G 的最大独立集

增广路

设 M 为一个匹配，若 P 是图 G 中一条连通两个未匹配顶点的路径，并且属于 M 的边和不属于 M 的边（即已匹配和待匹配的边）在 P 上交替出现，则称 P 为相对于 M 的一条增广路径。

增广路性质

将一条增广路上原来在匹配中的边从匹配中删去，不在匹配中的边加入匹配，则任然得到一个合法的匹配，且匹配的大小增加了1

匈牙利算法

• 主要思想

  1. 对于 X 集合的每个点，开始寻找增广路
  2. 如果找到了一条增广路，则进行增广

• 如何找到从一个点开始的增广路

  1. 对于每个点设立一个标记
  2. 在同一次找增广路的时候，如果一个点 v 这次没有找到增广路，则下一次也一定找不到
  3. 每个点之多访问一次 -> 时间复杂度 O(E)

• 总体时间复杂度 O(VE)

• 扩展

  1. KM算法（最优匹配）
  2. HK算法（O(E sqrt(V)) 最大匹配）

例题

ZOJ 1654 Place the Robots

题意

有一个N * M(N, M < 50) 的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙, 机器人只能放在空地上，在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击，问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。

思路

• 将每行被墙隔开且连续的一段称为一横块，同理每列的一段称为一纵块
• 一块内至多放一个机器人
• 每个方格属于一个横块和一个纵块
• 将方格看成边，块看成点，连边
  
  1. 选择若干个方格 -> 选择若干条边
  2. 一个块内至多放一个机器人 -> 与每个点相关的边至多只能选择一条
  3. 只能横块与纵块连边 -> 二分图
  4. 机器人最多 -> 边数最大 -> 最大匹配

AC代码