婚姻配对
   

　　你是一个婚姻中介公司的老板，你的主要任务是在男人与女人之间创造幸福的配对。

　　现在已有N个男人与N个女人在公司登记，他们想尽可能快的结婚。每个男人与女人都有一个对所有异性的偏爱列表。最偏爱的人出现在他（她）的偏爱列表的第一位，次偏爱的出现在列表的第二位，以此类推。下面的表格就是一个4个男子与4个女子偏爱列表：

　　

　　你的任务是设计一个关于所有男子与所有女子的配对，使得满足他们最多的偏爱。然而你必须假定，如果一个人被指定给另外一个人，那么他们的第一偏爱的人将十分的失望，只好选择在列表中更后的任一个人。如果这N对配对中存在一个男子与一个女子，他们并没有结成夫妇，但相对他们自己的伴侣更喜欢对方，那么这个配对被称为不稳定的。如果不存在这样的一对，则称为这个配对是稳定的。例如，这样配对"M1W3 M2W1 M3W4 M4W2 "是不稳定的，因为M1喜欢W1和W3，W1喜欢M1和M2。不稳定的一对在结婚后可能会容易分开；这的确是你要避免一种坏的情况。

　　通常对于给定的偏爱集合后，存在多种不同的稳定的配对，你的程序只要输出其中一种。

　　输入

　　输入包含T组测试数据，输入文件的第一行给出测试数据组数T。每个测试数据的第一行包含一个小于100的整数N。接下来N行N列表示N个男子的喜爱的女子的列表，再下来N行N列表示N个女子所喜爱的男子列表。假定所有男子与女子编号从1到N。

　　输出

　　对于每个测试数据，输出仅有一行，为所求的一个稳定的配对。每个配对用编号从小到大男子的对应的女子的编号表示。

　　Sample Input
　　2
　　6
　　6 1 4 5 2 3
　　2 3 5 4 1 6
　　2 1 5 3 6 4
　　4 5 6 2 3 1
　　6 3 4 5 2 1
　　6 4 1 3 5 2
　　5 6 4 2 3 1
　　4 6 1 5 3 2
　　5 4 3 1 6 2
　　4 3 1 6 2 5
　　5 3 4 6 2 1
　　3 2 6 4 5 1
　　3
　　1 2 3
　　3 2 1
　　2 1 3
　　1 2 3
　　3 2 1
　　2 1 3

　　Output for the Sample Input
　　2 5 1 4 3 6
　　1 3 2
　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有