The Stable Marriage Problem Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1966 Accepted: 838 Description The stable marriage problem consists of matching members of two different sets according to the member’s preferences for the other set’s members. The input for our problem consists of: a set M of n males; a set F of n females; for each male and female we have a list of all the members of the opposite gender in order of preference (from the most preferable to the least). A marriage is a one-to-one mapping between males and females. A marriage is called stable, if there is no pair (m, f) such that f ∈ F prefers m ∈ M to her current partner and m prefers f over his current partner. The stable marriage A is called male-optimal if there is no other stable marriage B, where any male matches a female he prefers more than the one assigned in A. Given preferable lists of males and females, you must find the male-optimal stable marriage. Input The first line gives you the number of tests. The first line of each test case contains integer n (0 < n < 27). Next line describes n male and n female names. Male name is a lowercase letter, female name is an upper-case letter. Then go n lines, that describe preferable lists for males. Next n lines describe preferable lists for females. Output For each test case find and print the pairs of the stable marriage, which is male-optimal. The pairs in each test case must be printed in lexicographical order of their male names as shown in sample output. Output an empty line between test cases. Sample Input 2 3 a b c A B C a:BAC b:BAC c:ACB A:acb B:bac C:cab 3 a b c A B C a:ABC b:ABC c:BCA A:bac B:acb C:abcSample Output a A b B c C a B b A c C有n個男士n個女士，每個人都對所有異性有一個評價值，男的對女的表白，如果女的沒有對象，就會接納這個男的，如果女的有對象但是女的對這個對象的好感不如表白這個人的好感，這個女的會拋棄現在的對象和對她表白的那個人在一起，要求出最穩定的婚姻狀態。 [cpp] #include<stdio.h> #include<string.h> #include<iostream> #include<queue> using namespace std; int male[30],female[30]; int m[30][30],fm[30][30]; int vis[30]; int n; char t[60]; queue<int> q; void scanf_name() { char tmp[30]; gets(t); //cout<<t <<endl; for(int i=0; i<n; i++) { gets(tmp); //cout<<tmp <<endl; int poit=tmp[0]-'a'+1; q.push(poit); for(int j=2; j<strlen(tmp); j++) { int k=tmp[j]-'A'+1; m[poit][j-1]=k; } } for(int i=0; i<n; i++) { //cout<<"cin"<<endl; gets(tmp); int poit=tmp[0]-'A'+1; for(int j=2; j<strlen(tmp); j++) { int k=tmp[j]-'a'+1; fm[poit][k]=j-1; } } } void GaleShapley() { while(!q.empty()) { int poit=q.front(); //第poit位男士 q.pop(); //if(male[poit]!=-1) //continue; if(vis[poit]>n) continue; int i=++vis[poit]; //第poit位男士最喜歡的第i位女士 //vis[poit]++; int fem=m[poit][i]; //第poit位男士最喜歡的第i為女士是第fem位 if(female[fem]==-1) //如果第fem位女士沒有喜歡的人 { female[fem]=poit; male[poit]=fem; continue; } else { int temp=female[fem]; if(fm[fem][temp]>fm[fem][poit]) //如果第fem位女士對當前喜歡的人的喜歡不如對第poit位男士的喜歡 { female[fem]=poit; male[poit]=fem; male[temp]=-1; q.push(temp); continue; } else { q.push(poit); continue; } } } } int main() { int s; scanf("%d",&s); while(s--) { memset(vis,0,sizeof(vis)); memset(male,-1,sizeof(male)); memset(female,-1,sizeof(female)); while(!q.empty()) q.pop(); scanf("%d",&n); getchar(); scanf_name(); GaleShapley(); int i=1; while(i<=n) { if(male[i]!=-1) printf("%c %c\n",i+'a'-1,male[i]+'A'-1); i++; } if(s) printf("\n"); } return 0; }
