Gale–Shapley算法代码C++

Gale-Shapley算法，也称为新娘选择算法，是一种解决稳定婚姻问题的数学模型。它假设每位男士都有一个优先级列表，按照他对女士们的喜好程度排序，而女士们则固定不动。算法以一种特定的方式让男士逐个向女士求婚，最终达到一个稳定匹配的状态，即没有任何一方愿意与其他已匹配的人交换。

以下是简单的Gale-Shapley算法在C++中的伪代码实现：

#include <iostream>
#include <vector>

// 假设Man和Woman类有相应的id、偏好列表等属性
class Man {
public:
    int id;
    std::vector<int> preferences;

    // 其他必要的构造函数和成员函数
};

class Woman {
public:
    int id;
    // 类似于Man，有偏好列表

    // 稳定匹配中的状态
    Man* partner = nullptr;
};

void gale_shapley(Man men[], Woman women[], int n) {
    for (Man& man : men) {
        // 为每个男人分配第一个女人
        man.partner = &women[man.preferences[0]];
        
        while (man.partner->partner != nullptr) { // 如果女士已经有伴侣
            if (man.id < man.partner->partner->id) { // 如果当前男人更喜欢未配对的女人
                Woman temp = *man.partner;
                man.partner = &women[man.preferences[temp.id]]; // 更新男人的首选
                women[temp.id].partner = nullptr; // 解除旧伴侣
            } else {
                man.partner->move_to_next(man); // 否则，男人向下一个女人求婚
            }
        }
    }
}

int main() {
    // 创建Man和Woman实例，并填充它们的数据
    Man men[]...;
    Woman women[]...;
    int n = sizeof(men)/sizeof(men[0]);

    gale_shapley(men, women, n);

    // 打印稳定匹配结果
    for (Man& man : men) {
        if (man.partner)
            std::cout << "Man " << man.id << " is paired with Woman " << man.partner->id << std::endl;
        else
            std::cout << "Man " << man.id << " is single" << std::endl;
    }

    return 0;
}