兩題都是基礎題，不同的是 zoj 那題的男女可能重名。

Gale-Shapley 算法：

while ( 存在男人m是自由的 ) {

　　　　令w是m的還沒求過婚的最高排名的女人

　　　　if ( w是自由的 ) ?m-w 配對

　　　　else ?{

　　　　　　　　取 w 的當前對象 m1

　　　　　　　　if ( w 更愛 m1 ) ? m保持自由

　　　　　　　　else ?m-w?配對 ?m1變成自由

　　　　}

}

?

?poj 3487

const int N = 105;int n; int hm[N], hw[N]; //hm[i]為第i個男人的配偶 -1表示自由 int a[N][N], b[N][N], p[N]; //a[i][0～n]表示第i個男人心中的女人排名//b[i][0～n]表示第i個女人心中的男人排名 string man[N], woman[N];//姓名 map<string, int> mp; //姓名->序號 set<int> st; //自由男人的集合void read(){mp.clear(); st.clear();memset(hm, -1, sizeof hm);memset(hw, -1, sizeof hw);memset(p, 0, sizeof p);cin>>n;FOR(i, 0, n){ cin>>man[i]; mp[ man[i] ] = i; }FOR(i, 0, n){ cin>>woman[i]; mp[ woman[i] ] = i; }string str, s="";int t;FOR(i, 0, n){cin>>str; s = str[0]; t = mp[s];FOR(j, 2, n+2){ s = str[j]; a[t][j-2] = mp[s]; }}FOR(i, 0, n){cin>>str; s = str[0]; t = mp[s];FOR(j, 2, n+2){ s = str[j]; b[t][j-2] = mp[s]; }} }void solve(){FOR(i, 0, n) {st.insert(i); } //開始所有男人都是自由的while( !st.empty() ){ //還有自由男人int m = *st.begin(); st.erase(m); //任取一個while(1){int w = a[m][ p[m]++ ]; //未拒絕此男人的最優女人int m1= hw[w], t; //此女人的配偶if(m1==-1){ hw[w]=m; hm[m]=w; break; } //女人自由FOR(i, 0, n) if(b[w][i]==m1 || b[w][i]==m) {t=b[w][i]; break;} //t是較優的男人if(t==m){ //m更優 重新組合hw[w]=m; hm[m]=w; hm[m1]=-1;st.insert(m1); break;}}} }int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);#endifint T;cin>>T;while(T--){read();solve();FOR(i, 0, n) cout<<man[i]<<' '<<woman[ hm[i] ]<<endl;cout<<endl;}return 0; }

?

?zoj 1576

const int N = 505;int n; int hm[N], hw[N]; //hm[i]為第i個男人的配偶 -1表示自由 int a[N][N], b[N][N], p[N]; //a[i][0～n] 男i心中的女人次序//b[i][0～n] 女i心中的男人次序 int c[N][N]; //c[i][j] 女i心中，男j的排名 string man[N], woman[N];//姓名 map<string, int> mp,wp; //姓名->序號 set<int> st; //自由男人的集合void read(){mp.clear(); wp.clear(); st.clear();memset(hm, -1, sizeof hm);memset(hw, -1, sizeof hw);memset(p, 0, sizeof p);string str;FOR(i, 0, n){cin>>man[i]; mp[ man[i] ] = i;if(i == 0)FOR(j, 0, n){cin>>woman[j]; wp[ woman[j] ] = j;a[i][j] = j;}elseFOR(j, 0, n){cin>>str;a[i][j] = wp[str];}}FOR(i, 0, n){cin>>str; int t = wp[str];FOR(j, 0, n){cin>>str;int v = mp[str];b[t][j] = v;c[t][v] = j;}} }void solve(){FOR(i, 0, n) {st.insert(i); } //開始所有男人都是自由的while( !st.empty() ){int m = *st.begin(); st.erase(m);while(1){int w = a[m][ p[m]++ ]; //未拒絕此男人的最優女人int m1 = hw[w]; //此女人的配偶if( m1 == -1 ){ hw[w]=m; hm[m]=w; break; } //女人無配偶if(c[w][m] < c[w][m1]){ //女人有配偶但m更優hw[w] = m; hm[m] = w; hm[m1] = -1;st.insert(m1); break;}}} }int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);#endifwhile(cin>>n){read();solve();FOR(i, 0, n) cout<<man[i]<<' '<<woman[ hm[i] ]<<endl;cout<<endl;}return 0; }

?

轉載于:https://www.cnblogs.com/ts65213/archive/2013/05/16/3082329.html

總結

以上是生活随笔為你收集整理的poj 3487 zoj 1576 稳定婚姻的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。