happy_lcj

题意：一个矩形中，有n个城市‘*’，‘o’表示空地，现在这n个城市都要覆盖无线，若放置一个基站， 那么它至多可以覆盖本身和相邻的一个城市，求至少放置多少个基站才能使得所有的城市都覆盖无线？ 思路：求二分图的最小路径覆盖（无向图） 最小路径覆盖=点数-最大匹配数 注：因为为无向图，每个顶点被算了两次，最大匹配为原本的两倍， 因此此时最小路径覆盖=点数-最大匹配数/2

题意：有一个n*n的矩阵,在矩阵上有m个行星,一个武器可以消灭同一行或者同一列的星星 求最小的要用多少武器消灭所有的星星 思路：把方阵看做一个特殊的二分图（以行列分别作为两个顶点集V1、V2，其中|V1|=|V2|） 然后把每行x或者每列y看成一个点，而障碍物(x,y)可以看做连接x和y的边。按照这种思路建图，问题就转化成为选择最少的一些

题意：有n个点和m条有向边，现在要在点上放一些伞兵，伞兵可以沿着图走， 直到不能走为止，每条边有且仅有一个伞兵走过，问最少放多少个伞兵 思路：求的最小路径覆盖，用二分图来做 对于这样的一个有向图做最小路径覆盖，首先建图 然后每一条有向边对应左边的点指向右边的点 这样建好图之后求最大匹配数 最小路径覆盖=点数-最大匹配数

题意：有n个学生，每个学生都和一些人有关系，现在要你找出最大的人数，使得这些人之间没关系 思路：求最大独立集，最大独立集=点数-最大匹配数 分析：建图时应该是一边是男生的点，一边是女生的点连边，但是题目中没说性别的问题，只能将每个点拆成两个点，一个当作是男的点，一个当作是女的点了，然后连边.由于关系是相互的，这样就造成了边的重复。也就是边集是刚才的二倍，从而导致了最大匹配变成了原本的二倍，因此，此时最大独立集=点数-最大匹配数/2.

二分图：二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联的两个顶点恰好一个属于集合X，另一个属于集合Y。 二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 最大匹配：图中包含边数最多的匹配称为图的最大匹配。 完美匹配：如果所有点都在匹配边上，则称这个最大匹配是完美匹配。 未盖