1059: [ZJOI2007]矩阵游戏 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5251 Solved: 2512 [Submit][Status][Discuss] Description 　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N *N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择 矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换 对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的 …

1191: [HNOI2006]超级英雄Hero Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5221 Solved: 2356 [Submit][Status][Discuss] Description 现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。 这里，我们把规则稍微改变一下。假设 …

学完了km..感觉匈牙利真是非常的。。easy... 匈牙利算法学习链接 有一种题目会用1*2的小格子填充大的，问能不能填满之类的，可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告 其实主要是关于建图的启示，上面两个题，还有这道题： poj1325解题报告 还有就是一些有用的结论： **(1)二分图的最小顶点覆盖 ** 最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。 Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。 (2)DAG图的最小路径覆盖 用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。 结论：DAG …

poj 3041题目链接 题意：一个nn的网格中，有k个大小为11的小行星，现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。 思路：一个建图技巧是：对于网格图，我们可以把某个格子的横纵坐标看成点，而格子所代表的内容看成边来建图。 如果我们按照这样的方式建图，那么这道题的行或者列就成了点，而小行星就成了边。我们要做得是选最少的点，使得这些点覆盖所有的边。 根据Knoig定理，二分图的最小顶点覆盖数等于二分图的最大匹配数。 匈牙利一遍即可。1A /* *********************************************** Author :111qqz …

poj1719题目链接 题意：射箭比赛，靶子是一个n*m的网格。网格的特点是没列只有两个白色，剩下的全是黑色。一共射m次，每列射一次，要求每行都射到至少一次才算合法，问是否有合法射法，如果有输出一组解。 思路：由于列数可能比行数多，那么我们把行编号作为左集合，列编号作为右集合，做一次匈牙利，对于每一行都找到它匹配的列，如果匹配数等于n，说明有解。对于输出一组街的问题，m列中已经匹配了n列，输出他们对应的link即可。对于剩下的m-n列，可以任意输出。由于之前不知道会剩下哪n-m列，所以在读入的时候有必要保存每一列的white格子的位置信息。 1A,有点爽。 /* …

hdu 4185题目链接 题意：给出一个nn的字符maze,‘.’代表水，‘#’代表油田。 挖油的机器一次会挖两个相邻方块。要求是必须两块必须都是油，不然会有杂质。问最多能挖多少次。 思路：和那道用12的小矩形块填充是一个思路。根据奇偶性对点标号，然后建图，匈牙利，2A. 第一遍是dfs写错了一个变量QAQ.a /* *********************************************** Author :111qqz Created Time :2016年05月30日 星期一 12时53分34秒 File Name :code/hdu/4185.cpp …

hdu 1068题目链接 题意：有n个同学。。给出同学之间的 爱慕关系。。。选出一个集合使得集合中的人没有爱慕关系。问能选出的最大集合是多少。 思路：没有数据范围，差评！题意说得也不清楚。。由数据知道。。爱慕关系一定是相互的。。。 这道题实际上是二分图的最大独立集问题。 **最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值** 学到的一点是：对于二分图，可能并不能明显得分成两个不相交的集合，而是一个整体。（有左集合到又集合的边，同时有又集合到左集合的边，就是说每条边都是无相边。。？） 这其实等于把两个无向图叠加在了一起（从左指向右的和从又指向左的） 所以hungary得到的最大匹配数应该除以2，才是 …

hdu 3225题目链接 题意：给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行，并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案，那么输出-1. 思路：有点像八皇后。。。就是纯搜。。。不过n好大。。。这么搜会TLE... 想了半天也没思路。。。看了题解。。发现是用二分图匹配来剪枝。。 比较重要的一点是。。。 n个数的某种排列，可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。 我们可以根据这个来剪枝。 具体做法： **我们先求出一个完备匹配，然后搜索每个位置能够种的花，假设当前位k置种了花i,那么判断k+1--n位 …

poj 1469 题目链接 题意：p个课程，n个学生，给出每个课程对应选取该课程的学生编号，问能否选出p个学生，使得和课程一一对应。 思路：一眼二分图最大匹配。。。需要注意的是。。两个集合可能分别给出。。建图的最大点数是两个集合的最大数目之和。。。因为没注意这个细节RE了一次。。 /* *********************************************** Author :111qqz Created Time :2016年05月26日 星期四 23时53分39秒 File Name :code/poj/1469.cpp …

poj 1325 题目链接 题意：有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组（i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启，问最少的重启次数。 思路：这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。 完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。 然后这道题就变成了二分图的最小顶点覆盖。 **二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最 …