网站里的动画效果图/网上怎么免费推广

对稳定婚姻问题的全面介绍：https://blog.csdn.net/a854596855/article/details/44631851

实现思路：https://blog.csdn.net/a854596855/article/details/44631851

这里给出两个结论：第一个是稳定婚姻一定存在；第二个是通过这种算法得出的婚姻必定是稳定且最优的，证明可以看下上面的博客。

Gale-Shapley算法：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;const int N=1e3+10;
queue<int> bachelor;//单身男士的队列 
int t, n;
int next[N], pref[N][N], admire[N][N], future_husband[N], future_wife[N];
//next[i]表示i男士下一个向谁求婚，pref[i][j]表示在i男士心目中排名第j的女士，admire[i][j]表示i女士心目中j男士的排名，future_husband[i]表示i未来的丈夫，future_wife[i]表示i未来的妻子 bool engage(int man, int woman) {if (!future_husband[woman]) {future_husband[woman]=man;future_wife[man]=woman;return true;}else {if (admire[woman][man]<admire[woman][future_husband[woman]]) {future_wife[future_husband[woman]]=0;bachelor.push(future_husband[woman]);future_husband[woman]=man;future_wife[man]=woman;return true;}else return false;}
} //一定有解，一定稳定 
int main() {cin >> t;while (t--) {memset(next, 0, sizeof(next));memset(pref, 0, sizeof(pref));memset(admire, 0, sizeof(admire));memset(future_husband, 0, sizeof(future_husband));memset(future_wife, 0, sizeof(future_wife));cin >> n;for (int i=1; i<=n; i++) {for (int j=1; j<=n; j++)cin >> pref[i][j];next[i]=1;future_wife[i]=0;bachelor.push(i);}for (int i=1; i<=n; i++) {for (int j=1; j<=n; j++) {int tmp;cin >> tmp;admire[i][tmp]=j;}future_husband[i]=0;}while (!bachelor.empty()) {int man=bachelor.front();bachelor.pop();int woman=pref[man][next[man]++];if (!woman) continue; if (!engage(man, woman)) bachelor.push(man);}for (int i=1; i<=n; i++)cout << future_wife[i] << " ";cout << endl;}return 0;
}