“发现有一个男人和一个女人没有成为夫妇，但他们彼此相爱更甚于自己的配偶”这句话没看懂：彼此间相爱的程度是怎么定义的呢？是男对女的偏爱度加上女对男的偏爱度呢，还是其他关系呢？

我感觉这个问题和八王后问题是一回事。或者说都可以用类似于全排列生成算法来解决。把男0~男n-1固定，然后用女0~女n-1来排列。只是这时候排列的约束条件为在男i这个位置为最稳定的女j(全排列是第i个位置上的数和第j个位置上的数不同).

下面我把男女间的相爱程度定义为双方对对方偏爱度相加来举个例子。
假如n 为4，并且有：
     MWR[4][4] ={{0,4,3,1  },{5,0,6,1  },{2,0,4,4  },{1,3,3,7  }}
     WMR[4][4] ={{1,4,1,7  },{2,5,1,6  },{2,0,1,4  },{8,3,6,1  }}
  1。 把男的位置全固定为0, 1, 2, 3. 然后把女的编号分别排列到这4个位置上。
  2。 求出每个位置和不同女之间的相爱度M[4][5]:M[i][j]表示 男i 和 女j 这两者之间的相爱度。 M[4][5] 其中的5比 女的总数多1， 这在后面是有用的。
      按照 相爱度 = 男对女的偏爱度 + 女对男的偏爱度 则有：
      M[i][j] = MWR[i][j] + WMR[i][j].
     M[4][5] = {{1,8,4,8,_},{7,5,7,7,_},{4,0,5,8,_},{9,6,9,8,_}}。其中的_表示 并不关心这个值是多少。
  3。 根据上面的相爱度表 M[i][j] 可以很容易知道，要想相成稳定的夫妻对， 那么能够放在 男i这个位置的 女 必须是 M[男i][j表示这n个女] 这一系列中的最大值。现在我们可以把M[i][j]这张表用做他用了：M[i] 这个数组表示 可以放在 男i 这个位置的 女的编号。用-1标记结束，这也就是在2中为什么要定义M[4][5]中的那个5的原因。现在    
      M[4][5] = {{1,3,-1},{0,2,3,-1},{3,-1},{0,2,-1}}.如其中的M[1]这个数组 的数据是 {0,2,3,-1}, 这表示能和 男1 组合成配偶的可以为 女0 女2 女3 ，其中-1标记结束。
  4。 核心部分：
      从 男0 这个位置考虑起，首先把 女1 放在这个位置上。并标记 女1 已经配对了。
        考虑 男1 这个位置， 把 女0 放在这个位置上。并标记 女0 已经配对了。
          考虑 男2 这个位置， 把 女3 放在这个位置上。并标记 女3 已经配对了。 
            考虑 男3 这个位置， 把 女0 放在这个位置上。但 女0 已经被标记配对了，不被允许
            (重新考虑 男3这个位置，用下一个可以放在这个位置上的 女2)
            考虑 男3 这个位置， 把 女2 放在这个位置上。并标记 女2 已经配对了。
          。。。。。。
     从上面，已经考虑到了 男方的所有位置了， 故上面这种配对是能满足要求的。故可以结束循环了。假设上面的 女2 还是被标记 已经配对了，那么 男3 这个位置 没有可以再 能配对的了，现在必须回溯 ：重新考虑 男2 这个位置；但男2 这个位置也没有可以配对的了，必须得再次回溯。 重新考虑 男1 这个位置，用下一个能和 男1 配对的 女。。。一直，直到全部都能配对 或着 男0 这个位置没有可以配对的了（这时候表示 不能全部都是 稳定的配对了。）

    注意，在回溯的时候，要记得解除标记这一次回溯的已标记的配对的 女方。