daily pastebin goal
50%
SHARE
TWEET

Stable matching

a guest Feb 22nd, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. #include <string.h>
  5.  
  6. using namespace std;
  7.  
  8. int ranking[505][505]; // Ranking gives the ranking of each man in the preference list of each woman
  9. int man_pref[505][505]; // man's preference list
  10. int woman_pref[505][505]; // woman's preference list
  11. int next[505]; // which woman will be proposed for each man
  12. int matches[505]; // the current engagement of each woman
  13.  
  14. int main(){
  15.     queue<int> freeMen;
  16.     int count , i , j ,w , m , current_woman , current_man;
  17.     scanf("%d" , &count);
  18.     for(i=1;i<=count;i++){
  19.         scanf("%d" , &w);
  20.         for(j=1 ; j <=count ; j++){
  21.             scanf("%d" , &woman_pref[w][j]);
  22.         }
  23.     } // initialize the preference list of woman
  24.  
  25.     for(i=1;i<=count;i++){
  26.         scanf("%d" , &m);
  27.         for(j=1 ; j <=count ; j++){
  28.             scanf("%d" , &man_pref[m][j]);
  29.         }
  30.     } // initialize the preference list of man
  31.  
  32.     for(i=1;i<=count;i++)
  33.         for(j=1;j<=count;j++)
  34.             ranking[i][woman_pref[i][j]] = j; // initialize ranking
  35.  
  36.     memset(matches , 0 , (count+1)*sizeof(int));
  37.  
  38.     for(i=1;i<=count;i++){
  39.         freeMen.push(i);
  40.         next[i] = 1;
  41.     }
  42.  
  43.     while(!freeMen.empty()){
  44.         current_man = freeMen.front();
  45.         current_woman = man_pref[current_man][next[current_man]];
  46.  
  47.         if(matches[current_woman] == 0){
  48.             matches[current_woman] = current_man;
  49.             freeMen.pop();
  50.         }
  51.         else if(ranking[current_woman][current_man] < ranking[current_woman][matches[current_woman]]){
  52.             int ex_man = matches[current_woman];
  53.             freeMen.pop();
  54.             matches[current_woman] = current_man;
  55.             freeMen.push(ex_man);
  56.         }
  57.  
  58.         next[current_man]++;
  59.     }
  60.  
  61.     for(i = 1 ; i <= count ; i++){
  62.         printf("man : %d , woman : %d get married!\n" , matches[i] , i);
  63.     }
  64.  
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top