稳定婚姻问题学习笔记

Gale-Shapley Algorithm

此算法的流程如下：
首先搞一个队列，存储未匹配的男士编号。每次取出一个未匹配的男士的编号，让他向其未求过婚的且最喜欢的女士求婚，如果对应女士没有匹配或者已经匹配的没有这位优，那么将这位与对应的女士相匹配，并且将原来已匹配的男士扔到队列里，一直重复上述步骤直到队列为空
可以证明，上述流程结束后，每位男士必定有配偶，且婚姻是稳定的

例题

1.UVA1175 Ladies' Choice
最简单的板子，直接上代码，抄的大刘的

#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 1000
int 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;
}

2.矩阵变换
不知道是怎么发现的一个性质
对于一行，它更喜欢这一行靠前的数
对于一个数，它更喜欢它的位置靠后的行
然后就转化为一个稳定婚姻问题了
关于上面的那条性质，这是一个例子：

0 1 0 2
1 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 200

int 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;
}
图论图论——稳定婚姻问题稳定婚姻问题

相关

图论---网络流

数的重心(图论深搜)

电子科技大学《图论及其应用》复习总结--第七章 图的着色

电子科技大学2017年《图论及其应用》试卷及答案

图论算法遍历基础

图论算法与模型（训练指南题库）

图论中的初始值

图论算法-最小生成树

LeetCode题解-07（简单图论）

图论学习笔记（二）

关于树（图论初步）

专题训练3-图论 - B - Learning Languages（并查集）

标签