hdu1914 The Stable Marriage Problem（稳定婚姻匹配）

题意：

有n个男的和n个女的，
对于每个男的和每个女的，都有一个异性名单，将自己喜好的人按优先级从高到低排列，
现在要求找到其中的一种稳定婚姻匹配方案，

不稳定的定义：
假如女a和男A匹配，如果存在男B，
满足男B更喜欢女a，同时女a相比男A更喜欢男B，那么女a就会和男B私奔。

数据范围：n<27，每个男的用一种小写字母代替(‘a’-‘z’)，每个女的用一个大写字母代替(‘A’-‘Z’)

解法：

一开始将所有男的丢入待匹配队列，
当队列不为空：
取出一个男的，
按照这个男的的优先表遍历这个男的未匹配过的女的，
1.如果女的未被匹配，那么就和这个男的匹配
2.如果女的已经被其他男的匹配，那么比较这个男的和已经匹配的男的比较，
如果比赢了即匹配，将已经匹配的移回队列，如果比输了就转到下一个女的重复操作，直到匹配成功。

算法一定存在完美匹配，这里不证明。

ps：
代码中有一个地方用指针优化就可以将复杂度优化为O(n²)，
但是我懒得写了。

code：

#include
using namespace std;
const int maxm=33;
int F[maxm],M[maxm];
int f[maxm][maxm];
int m[maxm][maxm];
int mark[maxm][maxm];
int fc[maxm];//F[i]当前匹配的
int mc[maxm];//M[i]当前匹配的
int n;
void cal(){memset(mark,0,sizeof mark);memset(fc,-1,sizeof fc);memset(mc,-1,sizeof mc);queue<int>q;for(int i=1;i<=n;i++){//将男的放入队列q.push(M[i]);}while(!q.empty()){int x=q.front();q.pop();for(int i=1;i<=n;i++){//遍历优先表,这里可以用指针优化省去无用遍历int v=m[x][i];if(mark[x][v])continue;//x以前和v匹配过,则跳过mark[x][v]=1;if(fc[v]==-1){//女的未被匹配,则直接匹配fc[v]=x;mc[x]=v;break;}else{if(f[v][x]>f[v][fc[v]]){//比较优先级q.push(fc[v]);//回去重新找fc[v]=x;mc[x]=v;break;}}}}
}
signed main(){int T;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++){//男名char t;cin>>t;M[i]=t-'a'+1;}for(int i=1;i<=n;i++){//女名char t;cin>>t;F[i]=t-'A'+1;}for(int i=1;i<=n;i++){//格式a:BACchar x,t;cin>>x>>t;x=x-'a'+1;for(int j=1;j<=n;j++){cin>>t;m[(int)x][j]=t-'A'+1;//这里存的是是优先表}}for(int i=1;i<=n;i++){//格式a:BACchar x,t;cin>>x>>t;x=x-'A'+1;for(int j=1;j<=n;j++){cin>>t;f[(int)x][t-'a'+1]=n-j+1;//这里存的是优先级}}cal();for(int i=1;i<=n;i++){cout<<(char)(M[i]+'a'-1)<<' '<<(char)(mc[F[i]]+'A'-1)<<endl;}if(T>=1)cout<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！