RT，該問題可解決n男n女配對(duì)問題：每個(gè)人有自己理想對(duì)象排名，而要使配對(duì)后不存在一對(duì)男女不是配偶且對(duì)于彼此的好感優(yōu)于當(dāng)前配偶。 算法流程： 1.每一輪未訂婚的男士向其未求過婚的女士求婚； 2.女士若有男士X向其求婚，如該女士之前沒有未婚夫，則直接將男士X作為該女士臨時(shí)的未婚夫，如已有未婚夫且對(duì)該男士X的好感比未婚夫更高，則把未婚夫甩了，重新加入單身狗隊(duì)列，把X作為未婚夫。 不斷執(zhí)行上述過程，知道所有男士均找到配偶為止。時(shí)間：O(n^2)
看上去對(duì)男士有點(diǎn)殘酷，但事實(shí)上這樣的流程可以保證男士當(dāng)前的配偶為可以找到的最好伴侶，畢竟之前求婚都已經(jīng)被拒絕；而女士只會(huì)找到可能找到最差的配偶，至于證明這里略去（好吧，其實(shí)是我不會(huì)，有興趣的可以看看這篇文章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)//定下臨時(shí)的配偶 { 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);//更優(yōu)則甩了當(dāng)前未婚夫 else q.push(man);//求婚失敗 } //while (!q.empty()) q.pop(); for (int i=0;i<n;i++) if (m[i])新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
