[Codechef] Stable Marriage Problem

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Stable Marriage Problem
Source            : Codechef
Category          : Data Structure
Algorithm         : Stable Marriage Problem
Verdict           : Accepted

1. #include "bits/stdc++.h"  
2.   
3. #define ll          long long int  
4. #define memo(a, b)  memset(a, b, sizeof a)  
5.   
6. static const int maxn = 500 * 5;  
7.   
8. int prefer[maxn][maxn], N, wPartner[maxn], mFree[maxn];  
9.   
10. bool wPreferM1OverM(int w, int m1, int m)  
11. {  
12.       for (int i = 1; i <= N; i++)  
13.       {  
14.             if (prefer[w][i] == m1) return true;  
15.             if (prefer[w][i] == m) return false;  
16.       }  
17. }  
18.   
19. void Stable_Marriage()  
20. {  
21.       memo(wPartner, -1);  
22.       memo(mFree, 0);  
23.       int freeCount = N;  
24.       while (freeCount)  
25.       {  
26.             int m;  
27.             for (m = 1; m <= N; m++)  
28.             {  
29.                   if (mFree[m] == 0) break;  
30.             }  
31.             for (int i = 1; i <= N && mFree[m] == 0; i++)  
32.             {  
33.                   int w = prefer[m][i];  
34.                   if (wPartner[w] == -1)  
35.                   {  
36.                         wPartner[w] = m;  
37.                         mFree[m] = 1;  
38.                         freeCount--;  
39.                   }  
40.                   else  
41.                   {  
42.                         int m1 = wPartner[w];  
43.                         if (wPreferM1OverM(w, m1, m) == false)  
44.                         {  
45.                               wPartner[w] = m;  
46.                               mFree[m] = 1;  
47.                               mFree[m1] = 0;  
48.                         }  
49.                   }  
50.             }  
51.       }  
52.       int woman[maxn];  
53.       for (int i = N; i <= 2 * N; i++)  
54.       {  
55.             woman[wPartner[i]] = i - N;  
56.       }  
57.       for (int i = 1; i <= N; i++)  
58.       {  
59.             printf("%d %d\n", i, woman[i]);  
60.       }  
61. }  
62.   
63. int main()  
64. {  
65.       int tc;  
66.       scanf("%d", &tc);  
67.       for (int tcase = 1; tcase <= tc; tcase++)  
68.       {  
69.             scanf("%d", &N);  
70.             // woman preferences  
71.             for (int i = 1; i <= N; i++)  
72.             {  
73.                   int w;  
74.                   scanf("%d", &w);  
75.                   w += N;  
76.                   for (int j = 1; j <= N; j++)  
77.                   {  
78.                         scanf("%d", &prefer[w][j]);  
79.                   }  
80.             }  
81.             // man preferences  
82.             for (int i = 1; i <= N; i++)  
83.             {  
84.                   int m;  
85.                   scanf("%d", &m);  
86.                   for (int j = 1; j <= N; j++)  
87.                   {  
88.                         int w;  
89.                         scanf("%d", &w);  
90.                         prefer[m][j] = w + N;  
91.                   }  
92.             }  
93.             Stable_Marriage();  
94.       }  
95. }