本文主要是介绍UVA 1175 - Ladies' Choice（稳定婚姻问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVA 1175 - Ladies' Choice
题目链接
题意：给定n个男人，n个女人，每个人心中对异性都有一个排序，从左往右是最喜欢到最不喜欢，然后现在要求一个稳定匹配，使得n对男女中，不存在男人对其他女人好感度大于配偶且女人对其他男人好感度大于配偶
思路：稳定婚姻问题，算法过程如下：
男人不断求婚，从最喜欢到最不喜欢，女人每次在求婚人中，选择一个最喜欢的配对，然后抛弃现在的配对，这个过程可以用一个队列存放求婚男人，这样直到队列为空，也就匹配完毕了
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;const int N = 1005;
int t, n;struct People {int order[N], now, match;
} man[N], woman[N];queue<int> Q;bool gao(int u, int v) {if (woman[v].match == -1) {woman[v].match = u;return true;} else if (woman[v].order[woman[v].match] > woman[v].order[u]) {man[woman[v].match].now++;Q.push(woman[v].match);woman[v].match = u;return true;}return false;
}int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);for (int i = 0; i < n; i++) {man[i].now = 0;for (int j = 0; j < n; j++) {scanf("%d", &man[i].order[j]);man[i].order[j]--;}Q.push(i);}for (int i = 0; i < n; i++) {woman[i].match = -1;int tmp;for (int j = 0; j < n; j++) {scanf("%d", &tmp);tmp--;woman[i].order[tmp] = j;}}while (!Q.empty()) {int u = Q.front();Q.pop();int v = man[u].order[man[u].now];if (!gao(u, v)) {man[u].now++;Q.push(u);}}for (int i = 0; i < n; i++)man[woman[i].match].match = i;for (int i = 0; i < n; i++)printf("%d\n", man[i].match + 1);if (t) printf("\n");}return 0;
}这篇关于UVA 1175 - Ladies' Choice（稳定婚姻问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
