首页 > 代码库 > HDU1914(稳定婚姻)
HDU1914(稳定婚姻)
http://acm.hdu.edu.cn/showproblem.php?pid=1914
思路:Gale-Shapley算法。算法过程是男士不停地求婚,女士不停地拒绝。在每一轮中,每个尚未订婚的男士在他还没有求过婚的女士中选一个自己最喜欢的求婚(不管她有没有订婚)。然后每个女士在向她求婚的人之中选择她最喜欢的一个订婚,并且拒绝其他人。注意,这些向她求婚的人中包含她的未婚夫,因此她可以选择另一个自己更喜欢的人订婚,而抛弃自己的现任未婚夫。这个算法的结果是使男士都能娶到自己有可能娶到的最好的妻子,所以是对男士的理想配对。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> using namespace std; struct male { int f,rev[41],tag; } m[41]; struct female { int tag,temp,val,wait[41]; } f[41]; int _,n,t,k,mf[41][41],fm[41][41]; char ch[41]; bool ok() { int i; for (i=1;i<=26;i++) if (m[i].f==0&&m[i].tag>0) return true; return false; } int main() { scanf("%d",&_); while (_--) { scanf("%d",&n); int i,j; for (i=1;i<=26;i++) { f[i].tag=0; m[i].tag=0; } for (i=1;i<=n;i++) { scanf("%s",ch); t=ch[0]-‘a‘+1; m[t].f=0; m[t].tag=t; memset(m[t].rev,0,sizeof(m[t].rev)); } for (i=1;i<=n;i++) { scanf("%s",ch); t=ch[0]-‘A‘+1; f[t].tag=t; f[t].temp=0; f[t].val=30; memset(f[t].wait,0,sizeof(f[i].wait)); } for (i=1;i<=n;i++) { scanf("%s",ch); t=ch[0]-‘a‘+1; for (j=2;j<=n+1;j++) mf[t][j-1]=ch[j]-‘A‘+1; } for (i=1;i<=n;i++) { //cout<<1; scanf("%s",ch); t=ch[0]-‘A‘+1; for (j=2;j<=n+1;j++) fm[t][j-1]=ch[j]-‘a‘+1; } //cout<<"hhhhhhh"<<endl; while (ok()) { for (i=1;i<=26;i++) { if (m[i].f==0&&m[i].tag>0) { for (j=1;j<=n;j++) { t=mf[i][j]; if (m[i].rev[t]==0) { m[i].rev[t]=1; m[i].f=1; k=++f[t].wait[0]; f[t].wait[k]=i; break; } } } } for (i=1;i<=26;i++) { if (f[i].tag>0) { for (j=1;j<=f[i].wait[0];j++) { t=f[i].wait[j]; for (k=1;k<=n;k++) if (fm[i][k]==t) break; if (f[i].val>k) { m[f[i].temp].f=0; f[i].temp=t; f[i].val=k; } else m[t].f=0; } f[i].wait[0]=0; } } } int out[41]; memset(out,0,sizeof(out)); for (i=1;i<=26;i++) if (f[i].tag>0) { j=f[i].temp; out[j]=i; } for (i=1;i<=26;i++) if (out[i]) printf("%c %c\n",i-1+‘a‘,out[i]-1+‘A‘); if (_) printf("\n"); } return 0; }
HDU1914(稳定婚姻)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。