除了在异性之间相互比较之外,每个人还会将自身加入到这个偏好顺序中。这表示,这个人只会接受与排在自身前面的异性匹配;这些异性称为 可接受的(acceptable)。显然,不可接受的异性的偏好顺序是无足轻重的;原则上,只需要给出可接受的异性之间的偏好顺序即可。所以,这些存在不可接受异性的偏好也称为列表不完整的偏好(preferences with incomplete lists)。
#include<iostream>#include<queue>#include<vector>// Solver for stable marriage problems.// Assume strict preferences with incomplete lists.structStableMatching{intnx,ny;std::vector<std::vector<int>>pref_x,pref_y;// Preferences: preferred first, only acceptable.std::vector<int>match_x,match_y;// Matching: -1 means unmatched.StableMatching(intnx,intny):nx(nx),ny(ny),pref_x(nx),pref_y(ny),match_x(nx,-1),match_y(ny,-1){}// Gale-Shapley algorithm.// Complexity: O(nx * ny).voidsolve(){// Compute Y's ranks over X.std::vector<std::vector<int>>ranks(ny,std::vector<int>(nx));for(intj=0;j!=ny;++j){for(inti=0;i!=pref_y[j].size();++i){ranks[j][pref_y[j][i]]=nx-i;}}// Initialize.std::vector<int>waitlist(ny);// Best proposal rank for j in Y.std::vector<int>ids(nx);// Next j in Y for i in X to propose to.std::queue<int>q;// Currently active i's in X.for(inti=0;i!=nx;++i)q.push(i);// Loop.while(!q.empty()){autoi=q.front();q.pop();autoj=pref_x[i][ids[i]++];if(ranks[j][i]>waitlist[j]){if(waitlist[j])q.push(pref_y[j][nx-waitlist[j]]);waitlist[j]=ranks[j][i];}else{q.push(i);}}// Output.for(intj=0;j!=ny;++j){if(waitlist[j]){inti=pref_y[j][nx-waitlist[j]];match_x[i]=j;match_y[j]=i;}}}};voidsolve(){// Input.intn;std::cin>>n;StableMatchingsolver(n,n);for(intj=0,x;j<n;++j){auto&cur=solver.pref_y[j];std::cin>>x;for(inti=0;i<n;++i){std::cin>>x;cur.push_back(x-1);}}for(inti=0,y;i<n;++i){auto&cur=solver.pref_x[i];std::cin>>y;for(intj=0;j<n;++j){std::cin>>y;cur.push_back(y-1);}}// Solve the problem.solver.solve();// Output.for(inti=0;i<n;++i){std::cout<<(i+1)<<' '<<(solver.match_x[i]+1)<<'\n';}}intmain(){std::ios::sync_with_stdio(false),std::cin.tie(nullptr);intt;std::cin>>t;for(;t;--t){solve();}return0;}
Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American mathematical monthly 69, no. 1 (1962): 9-15.
Irving, Robert W. "An efficient algorithm for the stable roommates problem." Journal of Algorithms 6, no. 4 (1985): 577-595.
Knuth, Donald Ervin. "Marriages stables." Technical report (1976).
McVitie, David G., and Leslie B. Wilson. "Stable marriage assignment for unequal sets." BIT Numerical Mathematics 10, no. 3 (1970): 295-309.
Roth, Alvin E., and Marilda Sotomayor. "Two-sided matching." Handbook of game theory with economic applications 1 (1992): 485-541.
Roth, Alvin E. "Deferred acceptance algorithms: History, theory, practice, and open questions." international Journal of game Theory 36, no. 3-4 (2008): 537-569.