Rejudge Progress:

1042: 帅小伙子和俊俏姑娘

Time Limit: 2000 MS Memory Limit: 65536 KB
Total Submit: 14 Accepted: 4 Page View: 696
Submit Status Discuss
南开大学冰火舞蹈团是一个云集帅小伙子和俊俏姑娘的地方。舞蹈团经常有演出任务。舞蹈团的团长需要给参加排练的同学做合适的舞伴配对,从而使整个节目能发挥出舞蹈团的较好的配合水平。 现在,有一个演出任务,需要n名帅小伙子与n名俊俏姑娘男女配对演出。当然,每个帅小伙子只能和一个俊俏姑娘配对成为舞伴。这n名帅小伙子,每个人对这n名俊俏姑娘在心里都有不同的排名,且任意两个姑娘在一个帅小伙子心目中的排名一定是不同的;同样,这n名俊俏姑娘每个人对这n名帅小伙子也都有不同的排名,且任意两个小伙子在一个俊俏姑娘心目中的排名一定是不同的。 根据舞蹈团梁团长的经验,如果一个配对组合,使得某位帅小伙子A的舞伴a在这位小伙子心目的排名不如另一位俊俏姑娘b,且这位俊俏姑娘b的舞伴B在她的心目中的排名不如这位帅小伙子A,那么帅小伙子A和俊俏姑娘b在排练的过程中就会有些情绪,演出效果可能就不大好。 现在,舞蹈团的梁团长听说你很聪明,想请你帮帮忙,在已知帅小伙子和俊俏姑娘们相互之间心目中的排名的前提下,告诉他是否存在一种合理的配对方案,使得所有的成员都能够在演出过程中不闹情绪?如果存在,请你帮他设计一组方案来为这些帅哥、靓妹们进行舞伴配对。
输入包括多组测试数据,你应当处理到输入结束为止。 每组输入数据的第一行是一个正整数n,n≤50,表示有多少对舞伴。 接下来有n行,每行有n个正整数,它们介于1到n,且互不相同,其中第i行的第j列表示第i个姑娘对第j个小伙子的排名。 再接下来还有n行,每行也有n个正整数,它们也介于1到n,且互不相同,其中第i行的第j列表示第i个小伙子对第j个姑娘的排名。
对于每组输入数据,输出两行。 对于第i组输入数据,输出的第一行为:”Case i:” 如果存在合适的配对方案,请输出的第二行输出一个由1到n之间互不相同的正整数组成的序列,相邻的两个正整数用一个空格隔开,第k个正整数表示第k个帅小伙子所配对的俊俏姑娘的编号,表示一种可行的配对方案;否则,请在输出的第二行输出”No Solution!”。
3 1 2 3 1 2 3 3 1 2 2 1 3 3 2 1 1 3 2 2 1 2 1 2 2 1 2 1
Case 1: 2 3 1 Case 2: 2 1