解题报告 http://blog.csdn.net/juncoder/article/details/38135053 题目传送门 题意： 给出NxN的矩阵，有M个点是障碍 每次只能删除一行或者一列，最少删除多少次才能清除障碍 思路： 把行和列看作两个集合结点，把障碍看作集合结点的连线，这样就转化成求用最少的点来消灭边，也就是最小点覆盖。 在二分图中：（n个结点，且

题意：n*n的格子里面有k个小行星，每一能消除一行或一列，那么最小消除多少次可以把全部消除掉 思路：把行和列连到一起，可以构成一个二分图，那么只需要求最大匹配数即为所求 <pre name="code" class="cpp">#include <iostream>#include <cstdio>#include <cstring>using namespace std;co

链接： NYOJ 237  游戏高手的烦恼：click here~~ POJ  3041 Asteroids           ：click here~~ 题意： 两题一样，翻译不同而已。 有一位传说级游戏高手，在闲暇时间里玩起了一个小游戏，游戏中，一个n*n的方块形区域里有许多敌人，玩家可以使用炸弹炸掉某一行或者某一列的所有敌人。他是种玩什么游戏都想玩得很优秀的人，所以，他决

http://poj.org/problem?id=3041 最小覆盖： 最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。 可以证明：最少的点（即覆盖数）＝最大匹配数 M 简单的证明如下： （1）M个是足够的。只需要让它们覆盖最大匹配的M条边，则其它边一定被覆盖（如果有边e不被覆盖，把e加入后得到一个更大的匹配） （2）M个是必需的，仅考虑形成最大匹配的这M条边

一、题目内容 POJ 3041 原题地址 二、题意解释 有一个N*N的网格,该网格有K个障碍物.你有一把武器,每次你使用武器可以清楚该网格特定行或列的所有障碍.问你最少需要使用多少次武器能清除网格的所有障碍物? 三、代码及注释 最小点覆盖=最大匹配 最大匹配：在二分图中最多能找到多少条没有公共端点的边 最小点覆盖：选择最少的点使得所有边都至少有一个端点被选中了，倒过来说就是，删除包含

http://poj.org/problem?id=3041 题意：给你长宽都有n个格子的矩阵，其中一些格子放着星球，现在可以一次 消除 一行或者一列的星球 求要让所有星球都消失的最少的次数。 #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#incl

题意： 空间中有很多颗小行星，飞船要每次能清空同一行或同一列上的所有小行星，问最少要几次能将所有小行星清除。 要点： 将小行星的行作为u，列作为v建图，就是一个最小点覆盖集的裸题，最小点覆盖集=最大匹配数，直接套个模板即可。 15480774Seasonal3041Accepted1164K32MSC++665B2016-05-08 10:16:33 #include<std

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 -------等等，看得头大？那么请看下面的版本： 通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异