UVALive3989 Ladies' Choice —— 稳定婚姻问题 Gale

题目链接：https://vjudge.net/problem/UVALive-3989

题解：

题意：有n个男生和n个女生。每个女生对男神都有个好感度排行，同时每个男生对每个女生也有一个好感度排行。问：怎样配对，才能使的每个女生尽可能幸福。规定在配对的过程中，如果一对男女不是舞伴，且他们喜欢对方的程度都大于当前的舞伴，那么他么会“私奔”，留下他们的舞伴孤零零。由于是要每个女生尽可能幸福，所以女生根据喜欢程度，主动去男生。而男生只能处于被动的状态。

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int MAXN = 1e3+;

 int pref[MAXN][MAXN], order[MAXN][MAXN], Next[MAXN];

 int future_husband[MAXN], future_wife[MAXN];

 queue<int>q;

 void engage(int woman, int man)

 {

     int w = future_wife[man];

     if(w)

     {

         future_husband[w] = ;

         q.push(w);

     }

     future_wife[man] = woman;

     future_husband[woman] = man;

 }

 int main()

 {

     int T, n;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d", &n);

         for(int i = ; i<=n; i++)

         {

             for(int j = ; j<=n; j++)

                 scanf("%d", &pref[i][j]);

             Next[i] = ;

             future_husband[i] = ;

             q.push(i);

         }

         for(int i = ; i<=n; i++)

         {

             for(int j = ; j<=n; j++)

             {

                 int x;

                 scanf("%d", &x);

                 order[i][x] = j;

             }

             future_wife[i] = ;

         }

         while(!q.empty())

         {

             int woman = q.front(); q.pop();

             int man = pref[woman][Next[woman]++];

             if(!future_wife[man])

                 engage(woman, man);

             else if(order[man][woman]<order[man][future_wife[man]])

                 engage(woman, man);

             else q.push(woman);

         }

         while(!q.empty()) q.pop();

         for(int i = ; i<=n; i++)

             printf("%d\n", future_husband[i]);

         if(T) printf("\n");

     }

 }

巴特西

UVALive3989 Ladies' Choice —— 稳定婚姻问题 Gale - Shapely算法

最新文章

热门文章