poj3041专题
POJ3041 最小顶点覆盖
N*N的矩阵，有些格子有物体，每次消除一行或一列，最少要几次消灭完。 行i - >列j 连边，表示(i,j)处有物体，即 边表示 物体。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;impo
NYOJ 237 游戏高手的烦恼 POJ3041-Asteroids ( 二分图的最大匹配 )
链接： NYOJ 237 游戏高手的烦恼：click here~~ POJ 3041 Asteroids ：click here~~ 题意： 两题一样，翻译不同而已。 有一位传说级游戏高手，在闲暇时间里玩起了一个小游戏，游戏中，一个n*n的方块形区域里有许多敌人，玩家可以使用炸弹炸掉某一行或者某一列的所有敌人。他是种玩什么游戏都想玩得很优秀的人，所以，他决
POJ3041 Asteroids(二分图)
题意： 空间中有很多颗小行星，飞船要每次能清空同一行或同一列上的所有小行星，问最少要几次能将所有小行星清除。 要点： 将小行星的行作为u，列作为v建图，就是一个最小点覆盖集的裸题，最小点覆盖集=最大匹配数，直接套个模板即可。 15480774Seasonal3041Accepted1164K32MSC++665B2016-05-08 10:16:33 #include<std
二分图的最大匹配 ————匈牙利算法 （转载了一个大神的趣味算法） poj3041(Asteroids)
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 -------等等，看得头大？那么请看下面的版本： 通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异