Gale–Shapley algorithm for Stable Marriage Problem


SUBMITTED BY: Guest

DATE: Nov. 12, 2013, 2:42 a.m.

FORMAT: Text only

SIZE: 2.6 kB

HITS: 954

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <queue>
  4. using namespace std;
  5. // Men and women are represented by integers 1...N
  6. // ManPref is the preference list of all men for all women.
  7. // ManPref[m][i] = w iff w is at ith position in the preference list of m
  8. // WomanPref is the preference list of all women for all men.
  9. // WomanPref[w][i] = m iff m is at ith position in the preference list of w
  10. // Ranking gives the ranking of each man in the preference list of each woman
  11. // Ranking[w][m] = i iff WomanPref[w][i] = m
  12. // Current gives the current engagement of each women
  13. // Current[w] = m iff w is currently engaged to m
  14. // Next gives the index of next woman to propose to in the preference list of each man
  15. // Next[m] = i iff m has proposed to all w s.t. ManPref[m][j] = w for j = 1...i-1 but not ManPref[m][i]
  16. int Ranking[505][505], ManPref[505][505], WomanPref[505][505], Next[505], Current[505];
  17. int main() {
  18. int T, N, i, j, m, w;
  19. // list of men who are not currently engaged
  20. queue <int> freeMen;
  21. scanf("%d", &T); // No. of test cases
  22. while (T--) {
  23. scanf("%d", &N); // No. of men and women
  24. for (i = 1; i <= N; i++) {
  25. scanf("%d", &w); // Woman number (b/w 1 and N) followed by her preference list
  26. for (j = 1; j <= N; j++)
  27. scanf("%d", &WomanPref[w][j]);
  28. }
  29. for (i = 1; i <= N; i++) {
  30. scanf("%d", &m); // Man number (b/w 1 and N) followed by his preference list
  31. for (j = 1; j <= N; j++)
  32. scanf("%d", &ManPref[m][j]);
  33. }
  34. for (i = 1; i <= N; i++)
  35. for (j = 1; j <= N; j++)
  36. Ranking[i][WomanPref[i][j]] = j;
  37. memset(Current, 0, (N + 1) * sizeof(int));
  38. for (i = 1; i <= N; i++) {
  39. freeMen.push(i);
  40. Next[i] = 1;
  41. }
  42. while (!freeMen.empty()) {
  43. m = freeMen.front();
  44. w = ManPref[m][Next[m]++];
  45. if (Current[w] == 0) {
  46. Current[w] = m;
  47. freeMen.pop();
  48. } else if (Ranking[w][m] < Ranking[w][Current[w]]) {
  49. freeMen.pop();
  50. freeMen.push(Current[w]);
  51. Current[w] = m;
  52. }
  53. }
  54. // (m, w) pairs in the stable matching
  55. for (w = 1; w <= N; w++)
  56. printf("%d %d\n", Current[w], w);
  57. }
  58. return 0;
  59. }

comments powered by Disqus