RT，该问题可解决n男n女配对问题：每个人有自己理想对象排名，而要使配对后不存在一对男女不是配偶且对于彼此的好感优于当前配偶。 算法流程： 1.每一轮未订婚的男士向其未求过婚的女士求婚； 2.女士若有男士X向其求婚，如该女士之前没有未婚夫，则直接将男士X作为该女士临时的未婚夫，如已有未婚夫且对该男士X的好感比未婚夫更高，则把未婚夫甩了，重新加入单身狗队列，把X作为未婚夫。 不断执行上述过程，知道所有男士均找到配偶为止。时间：O(n^2)
看上去对男士有点残酷，但事实上这样的流程可以保证男士当前的配偶为可以找到的最好伴侣，毕竟之前求婚都已经被拒绝；而女士只会找到可能找到最差的配偶，至于证明这里略去（好吧，其实是我不会，有兴趣的可以看看这篇文章http://blog.sina.com.cn/s/blog_8897e5420101bdr4.html）。 上代码：
//POJ3487#include <cstdio>#include <algorithm>#include <cstring>#define maxn 30#include <queue>using namespace std;int wife[maxn],now[maxn],husband[maxn],w[maxn],m[maxn],T,n,m_like[maxn][maxn],w_rank[maxn][maxn];queue <int> q;void engage(int man,int woman)//定下临时的配偶 { int tmp=husband[woman]; if (tmp!=-1) { q.push(tmp);//甩了要重新求婚~~~ wife[tmp]=-1; } wife[man]=woman; husband[woman]=man;}int main(){ scanf("%d",&T); while (T--) { scanf("%d/n",&n); memset(w,0,sizeof(w)); memset(m,0,sizeof(m)); char x; for (int i=0;i<n;i++) scanf("%c ",&x),w[x-'a']=1; for (int i=0;i<n;i++) scanf("%c ",&x),m[x-'A']=1; for (int i=0;i<n;i++) { char ch=getchar(),c; while (ch<'a'||ch>'z') ch=getchar(); c=getchar(); for (int j=0;j<n;j++) c=getchar(),m_like[ch-'a'][j]=c-'A';//男i第j喜欢的为m_like[i][j] q.push(ch-'a');now[ch-'a']=0;wife[ch-'a']=-1; } for (int i=0;i<n;i++) { char ch=getchar(),c; while (ch<'A'||ch>'Z') ch=getchar(); c=getchar(); for (int j=0;j<n;j++) c=getchar(),w_rank[ch-'A'][c-'a']=j;//女i喜欢的j排名为w_rank[i][j] husband[ch-'A']=-1; } while (!q.empty()) { int man=q.front();q.pop(); int woman=m_like[man][now[man]++]; if (husband[woman]==-1) engage(man,woman);//未订婚 else if (w_rank[woman][man]<w_rank[woman][husband[woman]]) engage(man,woman);//更优则甩了当前未婚夫 else q.push(man);//求婚失败 } //while (!q.empty()) q.pop(); for (int i=0;i<n;i++) if (m[i]) PRintf("%c %c/n",i+'a',wife[i]+'A'); printf("/n"); } return 0;}新闻热点
疑难解答
