? ? ? ? ? ?穩(wěn)定婚姻問題就是給你n個男的，n個女的，然后給你每個男生中女生的排名，和女生心目中男生的排名，然后讓你匹配成n對，使婚姻穩(wěn)定，假如a和b匹配,c和d匹配，如果a認為d比b好，同時d也認為a比c好，那么ad就有可能私奔，這樣就導(dǎo)致了婚姻的不穩(wěn)定，穩(wěn)定婚姻就是找到一種解決方案讓婚姻穩(wěn)定
算法：
? ? ? 穩(wěn)定婚姻的解決方法比較簡單，通俗易懂，而且還容易實現(xiàn)，具體有沒有固定的模板我不知道，沒有去找，自己模擬的，在求解的過程中，我們先把所有的男生都加到隊列里，隊列里的就表示當前還單身的男生，每次從隊列里拿出一個男生，然后從她最喜歡的女生開始匹配，如果當前的女生嘗試追求過，那么就不用追求了，如果當前的女生沒有伴侶，那么可以直接匹配上，如果有伴侶，那么就看看當前這個男生和女生之前的伴侶在那個女生中更喜歡誰，如果更喜歡當先的這個男生，那么當前男生就和這個女生匹配，女生之前匹配過的直接變成單身，被扔回隊列，否則，繼續(xù)找下一個女生，知道找到一個能匹配上的為止，就這樣一直到隊列空的時候，就已經(jīng)全部匹配完成了。

正確性：

? ? ? ? 對于男生來說，每次都是從最喜歡的女生開始匹配的，遇到的第一個沒人能搶走的并且穩(wěn)定的就是自己最終伴侶，也就是說如果之前追求過的女生被別人搶走了，那么他將永遠搶不會來，因為對于女生來說，第一次被男士按照自己的意愿選擇之后，每次變更匹配對象都是在自己心目中更加喜歡的，所以一旦他放棄了某個男生，那么那個男生就沒希望在和他匹配，這樣男生是從最優(yōu)的選的，保證男生不會出軌，女生每次都是在選擇她的男生中選擇最優(yōu)的，這樣也保證了女生最后沒有怨言，這樣的話，最后的到的婚姻就是穩(wěn)定的，至于穩(wěn)定婚姻，肯定會有穩(wěn)定方案，這個我暫時證明不了.<1962年，美國數(shù)學(xué)家 David Gale 和 Lloyd Shapley是這兩個人發(fā)明的方法，并且證明了穩(wěn)定婚姻一定會有解>。

?

?

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

#define N 30

using namespace std;

typedef struct
{
?? char a ,b;
}NODE;

NODE Ans[N];
int map[N][N] ,G_b[N][N];
int nowb[N] ,nowg[N];
char nameb[N] ,nameg[N];
int mark[N][N] ,ID[200];

bool camp(NODE a ,NODE b)
{
?? return a.a < b.a;
}

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

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);
???????? ID[str[0]] = i;
???????? nameb[i] = str[0];
????? }
????? for(i = 1 ;i <= n ;i ++)
????? {
???????? scanf("%s" ,str);
???????? ID[str[0]] = i;
???????? nameg[i] = str[0];
????? }
????? for(i = 1 ;i <= n ;i ++)
????? {
???????? scanf("%s" ,str);
???????? for(j = 2 ;j <= n + 1 ;j ++)
???????? map[ID[str[0]]][j-1] = ID[str[j]];
????? }
????? for(i = 1 ;i <= n ;i ++)
????? {
???????? scanf("%s" ,str);
???????? for(j = 2 ;j <= n + 1 ;j ++)
???????? G_b[ID[str[0]]][ID[str[j]]] = n - j + 2;
????? }
????? Marr(n);
????? for(i = 1 ;i <= n ;i ++)
????? Ans[i].a = nameb[i] ,Ans[i].b = nameg[nowb[i]];
????? sort(Ans + 1 ,Ans + n + 1 ,camp);
????? for(i = 1 ;i <= n ;i ++)
????? printf("%c %c\n" ,Ans[i].a ,Ans[i].b);
????? if(t) printf("\n");
?? }
?? return 0;
}
?????
?????

?

總結(jié)

以上是生活随笔為你收集整理的hdu1914 稳定婚姻问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。