? ? ?穩定婚姻問題就是給你n個男的，n個女的，然后給你每個男生中女生的排名，和女生心目中男生的排名，然后讓你匹配成n對，使婚姻穩定，假如a和b匹配,c和d匹配，如果a認為d比b好，同時d也認為a比c好，那么ad就有可能私奔，這樣就導致了婚姻的不穩定，穩定婚姻就是找到一種解決方案讓婚姻穩定

算法：

? ? ? 穩定婚姻的解決方法比較簡單，通俗易懂，而且還容易實現，具體有沒有固定的模板我不知道，沒有去找，自己模擬的，在求解的過程中，我們先把所有的男生都加到隊列里，隊列里的就表示當前還單身的男生，每次從隊列里拿出一個男生，然后從她最喜歡的女生開始匹配，如果當前的女生嘗試追求過，那么就不用追求了，如果當前的女生沒有伴侶，那么可以直接匹配上，如果有伴侶，那么就看看當前這個男生和女生之前的伴侶在那個女生中更喜歡誰，如果更喜歡當先的這個男生，那么當前男生就和這個女生匹配，女生之前匹配過的直接變成單身，被扔回隊列，否則，繼續找下一個女生，知道找到一個能匹配上的為止，就這樣一直到隊列空的時候，就已經全部匹配完成了。

正確性：
? ? ? ? 對于男生來說，每次都是從最喜歡的女生開始匹配的，遇到的第一個沒人能搶走的并且穩定的就是自己最終伴侶，也就是說如果之前追求過的女生被別人搶走了，那么他將永遠搶不會來，因為對于女生來說，第一次被男士按照自己的意愿選擇之后，每次變更匹配對象都是在自己心目中更加喜歡的，所以一旦他放棄了某個男生，那么那個男生就沒希望在和他匹配，這樣男生是從最優的選的，保證男生不會出軌，女生每次都是在選擇她的男生中選擇最優的，這樣也保證了女生最后沒有怨言，這樣的話，最后的到的婚姻就是穩定的，至于穩定婚姻，肯定會有穩定方案，這個我暫時證明不了，是看別人說的。

自己所以寫的一個模板，有點難看！！！！

#include<stdio.h>
#include<string.h>
#include<queue>

#define N 30

using namespace std;

int G_b[N][N];//男孩在女孩心中的分數?
int nowB[N] ,nowG[N]; //當前匹配結果?
char Name_B[N] ,Name_G[N]; //記錄名字?
int map[N][N];//男孩喜歡的女孩的順序?
int mark[N][N];//是否嘗試求婚過?
int hash[200];//mark名字用的?

void Marr(int n)
{
? ?queue<int>q;
? ?for(int i = 1 ;i <= n ;i ++)
? ?q.push(i);
? ?memset(nowB ,255 ,sizeof(nowB));
? ?memset(nowG ,255 ,sizeof(nowG));
? ?memset(mark ,0 ,sizeof(mark));
? ?while(!q.empty())
? ?{
? ? ? int tou = q.front();
? ? ? q.pop(); ?
? ? ? for(int ii = 1 ;ii <= n ;ii ++)
? ? ? {
? ? ? ? ?int i = map[tou][ii]; ?
? ? ? ? ?if(mark[tou][i]) continue;
? ? ? ? ?mark[tou][i] = 1;
? ? ? ? ?if(nowG[i] == -1)?
? ? ? ? ?{ ? ?
? ? ? ? ? ? nowG[i] = tou;
? ? ? ? ? ? nowB[tou] = i;
? ? ? ? ? ? break;
? ? ? ? ?}
? ? ? ? ?else
? ? ? ? ?{
? ? ? ? ? ? if(G_b[i][tou] > G_b[i][nowG[i]])
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? q.push(nowG[i]);
? ? ? ? ? ? ? ? nowG[i] = tou;
? ? ? ? ? ? ? ? nowB[tou] = i;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ?}
? ? ? }
? ?}
}


int main ()
{
? ?int t ,n ,i ,j;
? ?char str[30];
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d" ,&n);
? ? ? getchar();
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%s" ,str);
? ? ? ? ?hash[str[0]] = i;
? ? ? ? ?Name_B[i] = str[0];
? ? ? }
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%s" ,str);
? ? ? ? ?hash[str[0]] = i;
? ? ? ? ?Name_G[i] = str[0];?
? ? ? }?
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%s" ,str);
? ? ? ? ?for(j = 2 ;j <= n + 1 ;j ++)
? ? ? ? ?map[hash[str[0]]][j-1] = hash[str[j]];
? ? ? }
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%s" ,str);
? ? ? ? ?for(j = 2 ;j <= n + 1 ;j ++)
? ? ? ? ?G_b[hash[str[0]]][hash[str[j]]] = n - j + 2; ? ? ? ? ? ?
? ? ? }
? ? ? Marr(n);
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? printf("%c %c\n" ,Name_B[i] ,Name_G[nowB[i]]);
? ? ? if(t) puts("");
? ?}
? ?return 0;
}
? ? ? ? ?
? ? ? ? ? ??
? ?
? ? ??
? ? ??
? ? ? ? ?
? ? ??
? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ??
? ? ? ? ? ? ?
? ? ? ? ?
? ? ??
? ? ??
? ?
? ?
? ?
? ?
? ?

總結

以上是生活随笔為你收集整理的稳定婚姻问题（自己的总结）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。