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])新聞熱點
疑難解答
