稳定婚姻问题学习笔记-白红宇

稳定婚姻问题学习笔记

阅读量：5070 次

发布时间：2019-06-12

本文共 3647 字，大约阅读时间需要 12 分钟。

Gale-Shapley Algorithm

此算法的流程如下：

首先搞一个队列，存储未匹配的男士编号。每次取出一个未匹配的男士的编号，让他向其未求过婚的且最喜欢的女士求婚，如果对应女士没有匹配或者已经匹配的没有这位优，那么将这位与对应的女士相匹配，并且将原来已匹配的男士扔到队列里，一直重复上述步骤直到队列为空

可以证明，上述流程结束后，每位男士必定有配偶，且婚姻是稳定的

例题

最简单的板子，直接上代码，抄的大刘的

#include 
    
     #include  
     
      #include   
      
       #include   
       
        #include    
        
         #include    
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                using namespace std;#define ull unsigned long long#define pii pair
                
                 #define uint unsigned int#define mii map
                 
                  #define lbd lower_bound#define ubd upper_bound#define INF 0x3f3f3f3f#define IINF 0x3f3f3f3f3f3f3f3fLL#define DEF 0x8f8f8f8f#define DDEF 0x8f8f8f8f8f8f8f8fLL#define vi vector
                  
                   #define ll long long#define mp make_pair#define pb push_back#define re register#define il inline#define N 1000int pref[N+5][N+5], order[N+5][N+5], nxt[N+5];int futureHusband[N+5], futureWife[N+5];queue
                   
                     q;void engage(int man, int woman) { int m = futureHusband[woman]; if(m) { futureWife[m] = 0; q.push(m); } futureWife[man] = woman; futureHusband[woman] = man;}int main() { int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) scanf("%d", &pref[i][j]); nxt[i] = 1; futureWife[i] = 0; q.push(i); } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { int x; scanf("%d", &x); order[i][x] = j; } futureHusband[i] = 0; } while(!q.empty()) { int man = q.front(); q.pop(); int woman = pref[man][nxt[man]++]; if(!futureHusband[woman]) engage(man, woman); else if(order[woman][man] < order[woman][futureHusband[woman]]) engage(man, woman); else q.push(man); } while(!q.empty()) q.pop(); for(int i = 1; i <= n; ++i) printf("%d\n", futureWife[i]); if(T) printf("\n"); } return 0;}

不知道是怎么发现的一个性质

对于一行，它更喜欢这一行靠前的数

对于一个数，它更喜欢它的位置靠后的行

然后就转化为一个稳定婚姻问题了

关于上面的那条性质，这是一个例子：

0 1 0 21 0 2 0

行\(1\)喜欢的数的顺序：\(1\ 2\)

行\(2\)喜欢的数的顺序：\(1\ 2\)

数\(1\)对于行的喜欢顺序：\(1\ 2\)

数\(2\)对于行的喜欢顺序：\(1\ 2\)

如果行\(1\)和数\(2\)配对的话，就会出现行\(1\)更喜欢数\(1\)且数\(1\)更喜欢行\(1\)的情况，不合法，稳定婚姻算法可以避免这种情况的出现

代码：

#include 
    
     #include  
     
      #include   
      
       #include   
       
        #include    
        
         #include    
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                using namespace std;#define ull unsigned long long#define pii pair
                
                 #define uint unsigned int#define mii map
                 
                  #define lbd lower_bound#define ubd upper_bound#define INF 0x3f3f3f3f#define IINF 0x3f3f3f3f3f3f3f3fLL#define DEF 0x8f8f8f8f#define DDEF 0x8f8f8f8f8f8f8f8fLL#define vi vector
                  
                   #define ll long long#define mp make_pair#define pb push_back#define re register#define il inline#define N 200#define M 200int n, m;int matchx[N+5], matchy[N+5], a[N+5][2*N+5];int pref[N+5][N+5], order[N+5][N+5], nxt[N+5], head[N+5];queue
                   
                     q;void engage(int man, int woman) { int m = matchy[woman]; if(m) { matchx[m] = 0; q.push(m); } matchx[man] = woman; matchy[woman] = man;}int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); while(!q.empty()) q.pop(); for(int i = 1; i <= n; ++i) { nxt[i] = matchx[i] = matchy[i] = head[i] = 0; int tot = 0; for(int j = 1; j <= m; ++j) { scanf("%d", &a[i][j]); if(!a[i][j]) continue; pref[i][++tot] = a[i][j]; } q.push(i); } for(int j = m; j >= 1; --j) for(int i = 1; i <= n; ++i) if(a[i][j]) order[a[i][j]][i] = ++head[a[i][j]]; while(!q.empty()) { int u = q.front(); q.pop(); int v = pref[u][++nxt[u]]; if(!matchy[v]) engage(u, v); else if(order[v][u] < order[v][matchy[v]]) engage(u, v); else q.push(u); } for(int i = 1; i <= n; ++i) printf("%d ", matchx[i]); printf("\n"); } return 0;}

转载于:https://www.cnblogs.com/dummyummy/p/10833665.html

你可能感兴趣的文章