图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图,匈牙利算法是求解二分图最大匹配的一种方法,本文介绍相关内容。
图中的边均为无向无权边
图 1 是一个二分图。为了清晰,把它画成图 2 的形式。
在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。
例如,图 3、图 4 中红色的边就是图 2 的匹配。
它们的含义非常显然。
例如图 3 中 1、4、5、7 为匹配点,其他顶点为未匹配点;1-5、4-7为匹配边,其他边为非匹配边。
一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。
图 4 是一个最大匹配,它包含 4 条匹配边。
如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。
图 4 是一个完美匹配。显然,完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突)。但并非每个图都存在完美匹配。
最大匹配的匹配边的数目
选取最少的点,使任意一条边至少有一个端点被选择
对于一个 DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为 0(即单个点)。
选取最多的点,使任意所选两点均不相连
叫做
匈牙利算法
的事实上有两个算法,分别解决指派问题
和二分图最大匹配求解问题
,此处算法指求解二分图最大匹配的匈牙利算法。
从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。
例如,图 5 中的一条增广路如图 6 所示(图中的匹配点均用红色标出):
一般由 BFS 构造(类似于 BFS 树)。从一个未匹配点出发运行 BFS(唯一的限制是,必须走交替路),直到不能再扩展为止。
例如,由图 7,可以得到如图 8 的一棵 BFS 树:
这棵树(图8)存在一个叶子节点为非匹配点(7 号),但是匈牙利树要求所有叶子节点均为匹配点,因此这不是一棵匈牙利树; 但图 8 中根节点 2 到非匹配叶子节点 7 显然是一条增广路,沿这条增广路扩充后将得到一个完美匹配; 真正的匈牙利树如下图所示:
prev
数组。另外一个关于二分图的问题是求最小点覆盖:我们想找到最少的一些点,使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是,删除包含这些点的边,可以删掉所有边。
匈牙利算法可以用来解决一些看似无关的问题。
题目描述 小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个N×N 黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作: 行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的颜色) 列交换操作:选择矩阵的任意两列,交换这两列(即交换对应格子的颜色) 游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。 对于某些关卡,小Q百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!于是小Q决定写一个程序来判断这些关卡是否有解。 输入格式 第一行包含一个整数T,表示数据的组数。 接下来包含T组数据,每组数据第一行为一个整数N,表示方阵的大小;接下来N行为一个N×N 的01矩阵(0表示白色,1表示黑色)。 输出格式 包含T行。对于每一组数据,如果该关卡有解,输出一行Yes;否则输出一行No。
由M*N个格子组成, 其中某些格子凸起(灰色的格子)。每一次操作可以把某一行或某一列的格子给按下去。需要在限定次数把所有格子按下去,请计算出开给定的锁所需的最少次数。
读入/Input: 第一行 两个不超过100的正整数N, M表示矩阵的长和宽 以下N行 每行M个数 非0即1 1为凸起方格 输出/Output: 一个整数 所需最少次数
描述 Description 给出一张nn(n<=100)的国际象棋棋盘,其中被删除了一些点,问可以使用多少12的多米诺骨牌进行掩盖。 输入格式 Input Format 第一行为n,m(表示有m个删除的格子) 第二行到m+1行为x,y,分别表示删除格子所在的位置 x为第x行 y为第y列 输出格式 Output Format 一个数,即最大覆盖格数