【算法】黑白点的匹配

1、问题描述
设平面上分布着n个白点和n个黑点，每个点用一对坐标（x, y）表示。一个黑点b=（xb,yb）支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw。若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对）。在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。
2、具体要求
Input
输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含1个正整数n(n<16)；第二行含2n个实数xb1, yb1,xb2, yb2,…, xbn, ybn， (xbi, ybi)，i=1, 2, …, n表示n个黑点的坐标；第三行含2n个实数xw1, yw1,xw2, yw2,…, xwn, ywn，(xwi, ywi)，i=1, 2, …, n表示n个白点的坐标。同一行的实数之间用一个空格隔开。
Output
对于每个测试例输出一行，含一个整数，表示n个白点和n个黑点的最大匹配对数。
3、测试数据
Sample Input
1
3
5.0 3.0 5.0 -1.0 4.0 4.0
2.0 3.5 2.0 2.0 -2.0 -2.0
Sample Output
3

4、程序实现（Java语言）
  1/**
  2 * @(#)Ex5_2.java
  3 *
  4 *
  5 * @author 叶云策（intrl）
  6 * @version 1.00 2009/4/26
  7 */
  8
  9import java.io.*;
 10import java.util.*;
 11
 12public class Ex5_2
 13{
 14    public static void main(String[] args) throws Exception
 15    {
 16        Ex5_2 intrl=new Ex5_2();
 17        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 18        System.out.println("请输入测试例个数:");
 19        String str=br.readLine();
 20        int m=Integer.parseInt(str);
 21        intrl.Test(m);
 22    }
 23    
 24    public void Test(int m)
 25    {
 26        int[] result=new int[m];
 27        for(int i=0;i<m;i++)
 28        {
 29            try
 30            {
 31                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 32                System.out.println("总测试例个数为"+m+",现请输入第"+(i+1)+"个用例，数据由三行组成:");
 33                String str1=br.readLine();
 34                int n=Integer.parseInt(str1);
 35                String str2=br.readLine();
 36                String[] str3=str2.split(" ");
 37                String str4=br.readLine();
 38                String[] str5=str4.split(" ");
 39                
 40                Vector b=new Vector();
 41                Vector w=new Vector();
 42                for(int j=0;j<n;j++)
 43                {
 44                    b.add(j,new MyPoint(Float.parseFloat(str3[2*j]),Float.parseFloat(str3[2*j+1])));
 45                    w.add(j,new MyPoint(Float.parseFloat(str5[2*j]),Float.parseFloat(str5[2*j+1])));
 46                }
 47                result[i]=WB(w,b);
 48            }
 49            catch(IOException e)
 50            {
 51                System.out.println(e);
 52            }
 53        }
 54        System.out.println();
 55        System.out.println("结果：");
 56        for(int r=0;r<m;r++)
 57        {
 58            System.out.println(result[r]);
 59        }
 60    }
 61    public static int WB(Vector w,Vector b)/*核心算法*/
 62    {
 63        Collections.sort(w,new MyPoint.MyPointComparatorByXAC());
 64        Collections.sort(b,new MyPoint.MyPointComparatorByXAC());
 65        int pp=0;
 66        
 67        for(int i=w.size()-1;i>=0;i--)
 68        {
 69            MyPoint gpp=new MyPoint(-32768,-32768);
 70            for(int j=b.size()-1;j>=0;j--)
 71            {
 72                MyPoint mb=(MyPoint)b.get(j);
 73                MyPoint mw=(MyPoint)w.get(i);
 74                if(mb.getX()<mw.getX())
 75                {
 76                    break;
 77                }
 78                if(mb.getY()<mw.getY())
 79                {
 80                    continue;
 81                }
 82                if(gpp.getY()==-32768)
 83                {
 84                    gpp=mb;
 85                }
 86                else
 87                {
 88                    if(gpp.getY()<mb.getY())
 89                    {
 90                        gpp=mb;
 91                    }
 92                }
 93            }
 94            if(gpp.getY()!=-32768)
 95            {
 96                pp++;
 97            }
 98        }
 99        return pp;
100    }
101}
102
103class MyPoint //implements Comparable
104{
105    private float x;
106    private float y;
107    public void setX(float x)
108    {
109        this.x=x;
110    }
111    public float getX()
112    {
113        return x;
114    }
115    public void setY(float y)
116    {
117        this.y=y;
118    }
119    public float getY()
120    {
121        return y;
122    }
123    public MyPoint()
124    {
125    }
126    public MyPoint(float x,float y)
127    {
128        this.x=x;
129        this.y=y;
130    }
131    public static class MyPointComparatorByXAC implements Comparator
132    {
133        public int compare(Object o1,Object o2)
134        {
135            MyPoint p1=(MyPoint)o1;
136            MyPoint p2=(MyPoint)o2;
137            int result=(p1.getX()>p2.getX())?1:(p1.getX()==p2.getX()?0:-1);
138            return result;
139        }
140    }
141    public static class MyPointComparatorByYDESC implements Comparator
142    {
143        public int compare(Object o1,Object o2)
144        {
145            MyPoint p1=(MyPoint)o1;
146            MyPoint p2=(MyPoint)o2;
147            int result=(p1.getY()<p2.getY())?1:(p1.getY()==p2.getY()?0:-1);
148            return result;
149        }
150    }
151}

5、运行结果

posted on 2009-04-26 13:00 intrl 阅读(3184) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
<2009年4月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

随笔分类(55)

随笔档案(34)

网址收藏

资源下载

随笔导航

搜索

最新评论

阅读排行榜

评论排行榜