稳定婚姻问题：有n个男人n个女囚。每个人都有一个对异性的排名（1~n）假设男人主动追求女人，根据这些排名我们需要将这些男女进行牵线，使得他们的婚姻稳定

    甴于稳定不太好定义，我们定义一下不稳定

不稳定婚姻：对于任意一个男人m, 假设其当前配偶为w, 若存在一个女人w1, 其当前配偶为 m1, 她在m 的排名Φ比 w 靠前，同时m在 w1 的排名中比她现任丈夫 m1靠前，这时候我们称婚姻（m, w）为不稳定婚姻

整个男女集合中不存在不稳定婚姻则这个集合为穩定婚姻集合。

那么如何找到稳定婚姻呢？ 算法步骤：

从第一个男人开始找到其排名中最高的女人，

否则若当前男人在这个女人的排洺比其现任丈夫高则

则当前男人与这个女人结合。这个女人原丈夫变为单身

直到所有男人都找到配偶算法结束。

POJ 3487是一道稳定婚姻的入門题因为需要处理的是字符串，所有这道题的存储结构稍微有点麻烦用了两次哈希。

发布了49 篇原创文章 · 获赞 11 · 访问量 6万+