bzoj 1059: [ZJOI2007]矩阵游戏 (匈牙利算法)

1059: [ZJOI2007]矩阵游戏

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 5251  Solved: 2512
[Submit][Status][Discuss]

Description

  小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N
*N黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:行交换操作:选择
矩阵的任意两行,交换这两行(即交换对应格子的颜色)列交换操作:选择矩阵的任意行列,交换这两列(即交换
对应格子的颜色)游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑
色。对于某些关卡,小Q百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!!于是小Q决定写一个程
序来判断这些关卡是否有解。

Input

  第一行包含一个整数T,表示数据的组数。接下来包含T组数据,每组数据第一行为一个整数N,表示方阵的大
小;接下来N行为一个N*N的01矩阵(0表示白色,1表示黑色)。

Output

  输出文件应包含T行。对于每一组数据,如果该关卡有解,输出一行Yes;否则输出一行No。

Sample Input

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

Sample Output

No
Yes
【数据规模】
对于100%的数据,N ≤ 200
思路:
纠结了一下建图,由于每个黑点可以按照行换,也可以按照列换。所以我建了一个1..n到1..2n的二分图做匹配。
左边集合是n个对角线上的点,右边集合是行号+列号。
但是每次匹配的时候,一个对角线上的点会同时消耗到匹配的行号和列号。。感觉不是很对啊。。。
实际上发现,我们只需要建立一个n到n的二分图就行了。
原因是,如果有解,那么只需要行或者列的一种变换,就可以达到规定的图案。
比如现在(2,5)是1,(2,2)和(5,5)是0,我们只需要连一条边表示(2,5)可以换到(2,2)即可,不需要连表示(2,5)可以换到(5,5)的边
原因是,如果(2,5)换到(5,5),那么(2,2)也跟着换到了(5,2),我们不考虑之前的(2,2)是什么,被换之后的(2,2)必须是1才符合题意,也就是换之前的(5,2)必须是1.
既然(5,2)是1,那么从(5,2)换到(5,5)即可符合条件。

 

BZOJ 1191: [HNOI2006]超级英雄Hero (匈牙利)

1191: [HNOI2006]超级英雄Hero

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 5221  Solved: 2356
[Submit][Status][Discuss]

Description

现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目,只有当选手正确回答一道题后,才能进入下一题,否则就被淘汰。为了增加节目的趣味性并适当降低难度,主持人总提供给选手几个“锦囊妙计”,比如求助现场观众,或者去掉若干个错误答案(选择题)等等。 这里,我们把规则稍微改变一下。假设主持人总共有m道题,选手有n种不同的“锦囊妙计”。主持人规定,每道题都可以从两种“锦囊妙计”中选择一种,而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后,就一定能正确回答,顺利进入下一题。现在我来到了节目现场,可是我实在是太笨了,以至于一道题也不会做,每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”,那么你能告诉我怎样选择才能通过最多的题数吗?

Input

输入文件的一行是两个正整数n和m(0 < n <1001,0 < m < 1001)表示总共有n中“锦囊妙计”,编号为0~n-1,总共有m个问题。
以下的m行,每行两个数,分别表示第m个问题可以使用的“锦囊妙计”的编号。
注意,每种编号的“锦囊妙计”只能使用一次,同一个问题的两个“锦囊妙计”可能一样。

Output

第一行为最多能通过的题数p

Sample Input

5 6
3 2
2 0
0 3
0 4
3 2
3 2

Sample Output

4
思路: 从题目向2条锦囊妙计连边,注意判重。由于有一道题答错比赛就结束,因此在hung的过程中一旦不能find就直接break掉。

匈牙利算法总结

学完了km..感觉匈牙利真是非常的。。easy…
匈牙利算法学习链接

 

有一种题目会用1*2的小格子填充大的,问能不能填满之类的,可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告

其实主要是关于建图的启示,上面两个题,还有这道题: poj1325解题报告

还有就是一些有用的结论:

(1)二分图的最小顶点覆盖 

最小顶点覆盖要求用最少的点(X或Y中都行),让每条边都至少和其中一个点关联。

Knoig定理:二分图的最小顶点覆盖数等于二分图的最大匹配数。

(2)DAG图的最小路径覆盖

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点,这就是DAG图的最小路径覆盖问题。

结论:DAG图的最小路径覆盖数 = 节点数(n)- 最大匹配数(m)

(3)二分图的最大独立集

最大独立集问题: 在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

结论:二分图的最大独立集数 = 节点数(n)— 最大匹配数(m)

还有一个比较常用的角度:n个数的某种排列,可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。可以用来剪枝什么的。hdu3225解题报告

 

选区_079 选区_078

poj 3041 Asteroids (二分图的最小顶点覆盖,匈牙利算法)

poj 3041题目链接
题意:一个n*n的网格中,有k个大小为1*1的小行星,现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。

思路:一个建图技巧是:对于网格图,我们可以把某个格子的横纵坐标看成点,而格子所代表的内容看成边来建图。

如果我们按照这样的方式建图,那么这道题的行或者列就成了点,而小行星就成了边。我们要做得是选最少的点,使得这些点覆盖所有的边。

根据Knoig定理,二分图的最小顶点覆盖数等于二分图的最大匹配数。

匈牙利一遍即可。1A

 

poj 1719 Shooting Contest (匈牙利算法)

poj1719题目链接

题意:射箭比赛,靶子是一个n*m的网格。网格的特点是没列只有两个白色,剩下的全是黑色。一共射m次,每列射一次,要求每行都射到至少一次才算合法,问是否有合法射法,如果有输出一组解。

思路:由于列数可能比行数多,那么我们把行编号作为左集合,列编号作为右集合,做一次匈牙利,对于每一行都找到它匹配的列,如果匹配数等于n,说明有解。对于输出一组街的问题,m列中已经匹配了n列,输出他们对应的link即可。对于剩下的m-n列,可以任意输出。由于之前不知道会剩下哪n-m列,所以在读入的时候有必要保存每一列的white格子的位置信息。

1A,有点爽。

 

 

hdu 4185 Oil Skimming (二分图最大匹配,匈牙利算法)

hdu 4185题目链接
题意:给出一个n*n的字符maze,‘.’代表水,‘#’代表油田。 挖油的机器一次会挖两个相邻方块。要求是必须两块必须都是油,不然会有杂质。问最多能挖多少次。
思路:和那道用1*2的小矩形块填充是一个思路。根据奇偶性对点标号,然后建图,匈牙利,2A. 第一遍是dfs写错了一个变量QAQ.a

 

 

hdu 1068 Girls and Boys (二分图的最大独立集,匈牙利算法)

hdu 1068题目链接
题意:有n个同学。。给出同学之间的 爱慕关系。。。选出一个集合使得集合中的人没有爱慕关系。问能选出的最大集合是多少。

思路:没有数据范围,差评!题意说得也不清楚。。由数据知道。。爱慕关系一定是相互的。。。

这道题实际上是二分图的最大独立集问题。

最大独立集问题: 在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

 

学到的一点是:对于二分图,可能并不能明显得分成两个不相交的集合,而是一个整体。(有左集合到又集合的边,同时有又集合到左集合的边,就是说每条边都是无相边。。?) 这其实等于把两个无向图叠加在了一起(从左指向右的和从又指向左的)

所以hungary得到的最大匹配数应该除以2,才是真正的最大匹配数。

 

 

hdu 3225 Flowers Placement (dfs+匈牙利算法剪枝,太神了)

hdu 3225题目链接

 

题意:给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行,并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案,那么输出-1.

 

思路:有点像八皇后。。。就是纯搜。。。不过n好大。。。这么搜会TLE…

想了半天也没思路。。。看了题解。。发现是用二分图匹配来剪枝。。

比较重要的一点是。。。

n个数的某种排列,可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配

我们可以根据这个来剪枝。

具体做法:

我们先求出一个完备匹配,然后搜索每个位置能够种的花,假设当前位k置种了花i,那么判断k+1–n位置能不能形成一个完备匹配(即能否种出满足条件的花),若能那么当前位置可以种该花,继续搜索,若不能这返回

 

然后把一个false写了true.调了一个小时。。。。。。。。。。。。。。无语凝噎。

 

poj 1469 COURSES (匈牙利算法)

poj 1469 题目链接

题意:p个课程,n个学生,给出每个课程对应选取该课程的学生编号,问能否选出p个学生,使得和课程一一对应。

思路:一眼二分图最大匹配。。。需要注意的是。。两个集合可能分别给出。。建图的最大点数是两个集合的最大数目之和。。。因为没注意这个细节RE了一次。。

 

 

poj 1325 Machine Schedule(二分图的最小顶点覆盖,匈牙利算法)

poj 1325 题目链接
题意:有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组(i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启,问最少的重启次数。

 

思路:这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。

完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。

 

然后这道题就变成了二分图的最小顶点覆盖。

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

根据Knoig定理:二分图的最小顶点覆盖数等于二分图的最大匹配数。

一个证明:二分图最小顶点覆盖的证明

 

剩下的就是裸的hungary..

然而WA了好几次。。。

一个小细节没处理好。。。

由于初始是模式0.。。

所以模式0肯定要特殊考虑。。。因为初始状态是没有重启的。。。

但是我错误得以为只有当存在(i,0,0)这样的边时才忽略不算。。。

但是其实只要有一个端点是0就好了啊。。。不管哪端是0,我就用这个0来完成工作。。。依然不增加重启次数。。。

这不是什么坑点。。。脑袋秀逗了。。。

 

 

poj 1422 Air Raid (DAG的最小路径覆盖,匈牙利算法)

poj 1422题目链接

题意+思路:DAG的最小路径覆盖。。。匈牙利算法。。。poj 2594的低配版。。

 

poj 2594 Treasure Exploration (DAG图最小路径覆盖变形,匈牙利算法+floyd求传递闭包)

poj 2594 题目链接

题意:一个DAG图,每个点有宝藏…可以降落任意个机器人到任意点…然后机器人可以沿着路径走,路过某个点的时候,可以取走该点的宝藏。问要取走所有宝藏,最少需要多少个机器人。

思路:乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过一次的。。而这道题路过某个点的时候,可以不取走宝藏。。以及题面里明确说了“you should notice that the roads of two different robots may contain some same point.

那是否还可以用最小路径覆盖做呢。。答案是可以的。。。

区别就在于一个点如果被一条路径使用过一次,还可不可以使用第二次。。。

如果我们按照传统的DAG图的最小路径覆盖考虑。。。如果一个点会被路径经过两次。。。那么我们不妨增加一个点。。。 进一步考虑。。。我们要的是尽可能覆盖所有点。。。如果这条路径前后的点不会因为这个点而中断,那么这个增设点是否存在,其实是无所谓的,只要改点前后的点连通性不受影响即可。 说到连通性,不禁想到floyd求传递闭包。

 

然后对于DAG图的最小路径覆盖问题。。。就可以用hungary算法求解。。。

ans = n – 最大匹配数。

这应该算作hungary的一个应用。

 

poj 2446 Chessboard (匈牙利算法)

poj 2446 题目链接
题意:一个n*m的矩形方格里,有k个坏点,然后问能否用1*2的矩形块将矩形方格填满。坏点不能填,小的矩形块不能重叠,不能超出边界。不能有好点没有被填。

思路:乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法(横着放,竖着放) 可能我们对于第i个,可以横着放,也可以竖着放,但是可能某种方案使得后面的某一块没办法放置,因此我们需要反过来调整第i块的放法。  这个过程似乎和二分图匹配有点类似。。?  那到底有没有相似点呢。。。又如何划分集合呢。。。?

如果每个小方格看做点,能不能填满,其实就等价与这些点的最大匹配数×2+坏点数=m*n是否成立。。。那如何划分集合呢。。。? 我们可以根据点的坐标的奇偶性划分集合。。。因为小矩形块是2*1的,所以容易知道,每块矩形块放置的两个点一定属于不同的集合。。这样就满足了二分图匹配问题的模型。。。

然后匈牙利搞之。

 

这题一开始WA了。。WA在没有注意到一个小细节,使得连边的时候,有的是左点指向右点,而有的连成了右点指向左点。

 

 

poj 1274 The Perfect Stall (匈牙利算法)

poj 1274题目链接

裸的匈牙利。

hdu 2063 过山车 (匈牙利算法模板题)

hdu2063题目链接

题意:求二分图最大匹配。

思路:匈牙利算法。

通过这三篇博客了解了相关概念,学习了匈牙利算法。
趣写算法系列之–匈牙利算法
二分图的最大匹配、完美匹配和匈牙利算法
匈牙利算法详解

 

感受就是:这个是相对容易学的算法。。并没有名字那么不明觉厉。。。

主体就是一个dfs的过程。。。。

不过据说有比较多的应用。

所以打算切一些题目加深理解以后再回来总结。