文件名称:white_black
- 所属分类：
- 数据结构常用算法
- 资源属性：
- [Windows] [Visual C] [源码]
- 上传时间：
- 2012-11-26
- 文件大小：
- 367kb
- 下载次数：
- 0次
- 提 供 者：
- zac****
- 相关连接：
- 无
- 下载说明：
- 别用迅雷下载，失败请重下，重下不扣分！
介绍说明－－下载内容均来自于网络，请自行研究使用
1、问题描述
设平面上分布着n个白点和n个黑点,每个点用一对坐标(x, y)表示.一个黑点b=(xb,yb)支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw.若黑点b支配白点w,则黑点b和白点w可匹配(可形成一个匹配对).在一个黑点最多只能与一个白点匹配,一个白点最多只能与一个黑点匹配的前提下,求n个白点和n个黑点的最大匹配对数.
2、具体要求
要求:时间效率在O(NlgN)
3、实现方法
基于贪心算法
以x坐标的升序对黑点排序(可用QUICKSORT或者HEAPSORT),对白点生成一个小根堆!-1 Descr iption of the problem based on the distribution of plane n-n-white spots and black spots, each point with a pair of coordinates (x, y) said. A black point b = (xb, yb) dominating a white point w = ( xw, yw) if and only if xb> = xw and yb> = yw. If the black point b dominant white w, then the black point and white point w b can match (which can form a matched pair). in a black spot at most can only be matched with a white spot, a white point can only match with the premise of a black point, find the n-n-white spots and black spots on the maximum number of matches. 2, specific requirements requirements: time efficiency in the O ( NlgN) 3, Implementation of the greedy algorithm based on x coordinates in ascending order of black spots (available QUICKSORT or HEAPSORT), generating a small white spot root heap!
设平面上分布着n个白点和n个黑点,每个点用一对坐标(x, y)表示.一个黑点b=(xb,yb)支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw.若黑点b支配白点w,则黑点b和白点w可匹配(可形成一个匹配对).在一个黑点最多只能与一个白点匹配,一个白点最多只能与一个黑点匹配的前提下,求n个白点和n个黑点的最大匹配对数.
2、具体要求
要求:时间效率在O(NlgN)
3、实现方法
基于贪心算法
以x坐标的升序对黑点排序(可用QUICKSORT或者HEAPSORT),对白点生成一个小根堆!-1 Descr iption of the problem based on the distribution of plane n-n-white spots and black spots, each point with a pair of coordinates (x, y) said. A black point b = (xb, yb) dominating a white point w = ( xw, yw) if and only if xb> = xw and yb> = yw. If the black point b dominant white w, then the black point and white point w b can match (which can form a matched pair). in a black spot at most can only be matched with a white spot, a white point can only match with the premise of a black point, find the n-n-white spots and black spots on the maximum number of matches. 2, specific requirements requirements: time efficiency in the O ( NlgN) 3, Implementation of the greedy algorithm based on x coordinates in ascending order of black spots (available QUICKSORT or HEAPSORT), generating a small white spot root heap!
(系统自动生成,下载前可以参看下载内容)
下载文件列表
2008301500209：黑白点问题\1.cpp
.........................\1.dsp
.........................\1.dsw
.........................\1.ncb
.........................\1.opt
.........................\1.plg
.........................\2008301500209：黑白点问题\1.cpp
.........................\.........................\1.dsp
.........................\.........................\1.dsw
.........................\.........................\1.ncb
.........................\.........................\1.opt
.........................\.........................\1.plg
.........................\.........................\Debug\1.exe
.........................\.........................\.....\1.ilk
.........................\.........................\.....\1.obj
.........................\.........................\.....\1.pch
.........................\.........................\.....\1.pdb
.........................\.........................\.....\vc60.idb
.........................\.........................\.....\vc60.pdb
.........................\.........................\resource.h
.........................\.........................\Script1.rc
.........................\.........................\Script2.rc
.........................\Debug\1.exe
.........................\.....\1.ilk
.........................\.....\1.obj
.........................\.....\1.pch
.........................\.....\1.pdb
.........................\.....\vc60.idb
.........................\.....\vc60.pdb
.........................\resource.h
.........................\Script1.rc
.........................\Script2.rc
.........................\2008301500209：黑白点问题\Debug
.........................\2008301500209：黑白点问题
.........................\Debug
2008301500209：黑白点问题
.........................\1.dsp
.........................\1.dsw
.........................\1.ncb
.........................\1.opt
.........................\1.plg
.........................\2008301500209：黑白点问题\1.cpp
.........................\.........................\1.dsp
.........................\.........................\1.dsw
.........................\.........................\1.ncb
.........................\.........................\1.opt
.........................\.........................\1.plg
.........................\.........................\Debug\1.exe
.........................\.........................\.....\1.ilk
.........................\.........................\.....\1.obj
.........................\.........................\.....\1.pch
.........................\.........................\.....\1.pdb
.........................\.........................\.....\vc60.idb
.........................\.........................\.....\vc60.pdb
.........................\.........................\resource.h
.........................\.........................\Script1.rc
.........................\.........................\Script2.rc
.........................\Debug\1.exe
.........................\.....\1.ilk
.........................\.....\1.obj
.........................\.....\1.pch
.........................\.....\1.pdb
.........................\.....\vc60.idb
.........................\.....\vc60.pdb
.........................\resource.h
.........................\Script1.rc
.........................\Script2.rc
.........................\2008301500209：黑白点问题\Debug
.........................\2008301500209：黑白点问题
.........................\Debug
2008301500209：黑白点问题