舞伴问题数据结构c++

舞伴问题是一个经典的稳定婚姻问题，可以使用C++中的结构体和数组来实现。

首先，定义一个结构体来表示人员的信息，包括姓名、性别、喜欢的异性类型和当前的舞伴等信息。

struct Person {
    string name; // 姓名
    bool gender; // 性别，0表示女性，1表示男性
    vector<int> pref; // 喜欢的异性类型，pref[i]表示第i个异性的编号
    int partner; // 当前的舞伴编号，-1表示没有舞伴
};

然后，定义一个数组来存储所有人员的信息，以及一个辅助数组来记录每个人当前还没有被匹配的最优异性的编号。

const int MAXN = 1005;
Person man[MAXN], woman[MAXN]; // 男女数组
int next[MAXN]; // next[i]表示第i个男性还没有被匹配的最优女性编号

接下来，可以实现一个简单的匹配算法，如Gale-Shapley算法：

void gale_shapley(int n) {
    queue<int> q; // 存放还没有找到舞伴的男性
    for (int i = 0; i < n; i++) {
        q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); // u是当前还没有找到舞伴的男性编号
        q.pop();
        int v = man[u].pref[next[u]]; // v是u喜欢的尚未拒绝的最优女性编号
        if (woman[v].partner == -1) { // 如果v没有舞伴
            woman[v].partner = u; // v和u成为舞伴
            man[u].partner = v;
        } else if (woman[v].pref[woman[v].partner] < woman[v].pref[u]) { // 如果v拒绝u并且更喜欢当前的舞伴
            q.push(u); // u重新进入队列
        } else { // 如果v拒绝u并且更喜欢u
            man[woman[v].partner].partner = -1; // v和原来的舞伴分手
            woman[v].partner = u; // v和u成为舞伴
            man[u].partner = v;
            q.push(woman[v].partner); // 原来的舞伴重新进入队列
        }
        next[u]++; // u的下一个选择
    }
}

最后，调用这个算法来匹配所有的男女。

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string name;
        bool gender;
        vector<int> pref;
        cin >> name >> gender;
        for (int j = 0; j < n; j++) {
            int p;
            cin >> p;
            pref.push_back(p - 1);
        }
        if (gender) {
            man[i].name = name;
            man[i].gender = gender;
            man[i].pref = pref;
            man[i].partner = -1;
            next[i] = 0;
        } else {
            woman[i].name = name;
            woman[i].gender = gender;
            woman[i].pref = pref;
            woman[i].partner = -1;
        }
    }
    gale_shapley(n);
    for (int i = 0; i < n; i++) {
        cout << man[i].name << " " << woman[man[i].partner].name << endl;
    }
    return 0;
}

这个程序可以读入每个人的信息，然后使用Gale-Shapley算法来匹配所有的男女，并输出每个男性和他的舞伴。