HDOJ1914解题报告【稳定婚姻模板】

题目地址：
　　http://acm.hdu.edu.cn/showproblem.php?pid=1914
题目概述：
　　给出n个男性和n个女性以及他们对其他人做自己伴侣的期望，求匹配方案使尽可能多的人满意。
大致思路：
　　题意可能没怎么讲清吧，不过这题是稳定婚姻算法的模板题。
代码：
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <vector>
  6 #include <ctime>
  7 #include <map>
  8 #include <stack>
  9 #include <set>
 10 #include <queue>
 11 #include <cstring>
 12 #include <algorithm>
 13 using namespace std;
 14 
 15 #define sacnf scanf
 16 #define scnaf scanf
 17 #define maxn 55
 18 #define maxm 26
 19 #define inf 1061109567
 20 #define Eps 0.000001
 21 const double PI=acos(-1.0);
 22 #define mod 1000000007
 23 #define MAXNUM 10000
 24 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
 25 int Abs(int x) {return (x<0)?-x:x;}
 26 typedef long long ll;
 27 
 28 map<char,int> man,woman;
 29 map<int,char> turn;
 30 char temp[maxn];
 31 
 32 int a[maxn][maxn],b[maxn][maxn],n; //a-->男生的期望   b-->女生的期望
 33 int ans[maxn];   //每位男生选中的女生
 34 int manStartPos[maxn];//记录每位男生选取的是心目中第几位的女生
 35 int ladayNow[maxn];//女生对应的男生
 36 
 37 int GetPositionFromLaday(int laday, int man)
 38 {
 39     for(int i=1;i<=n;i++)
 40         if(b[laday][i]==man)
 41             return i;
 42     return -1;
 43 }
 44 
 45 void ChoosePartener(stack<int>& S, int manPos)
 46 {
 47     //选择自己名单上排在首位的女人
 48     int perferLaday = a[manPos][manStartPos[manPos]];
 49     //如果该女孩没有接受过表白，则接受该男孩的表白
 50     if(ladayNow[perferLaday]==-1)
 51     {
 52         ladayNow[perferLaday]=manPos;
 53         ans[manPos]=perferLaday;
 54     }
 55     //如果已经有人向她表白，则判断其现在拥有的有没有现在追求的好
 56     else
 57     {
 58         int oldPos=GetPositionFromLaday(perferLaday,ladayNow[perferLaday]);
 59         int newPos=GetPositionFromLaday(perferLaday,manPos);
 60         if(oldPos<newPos)
 61         {
 62             manStartPos[manPos]++;//说明该女生更喜欢现在拥有的，选心目中第二位
 63             //加入单身行列
 64             S.push(manPos);
 65         }
 66         else //换男友
 67         {
 68             //被甩的男友恢复自由身份
 69             manStartPos[ladayNow[perferLaday]]++;
 70             //加入单身行列
 71             S.push(ladayNow[perferLaday]);
 72             //将追求的男士改为现任男友
 73             ladayNow[perferLaday]=manPos;
 74             ans[manPos]=perferLaday;
 75         }
 76     }
 77 }
 78 
 79 void solve()
 80 {
 81     memset(ladayNow,-1,sizeof(ladayNow));
 82     memset(manStartPos,0,sizeof(manStartPos));
 83     memset(ans,0,sizeof(ans));
 84 
 85     stack<int> S; // 还处于单身的男士
 86 
 87     //进行第一轮迭代，每个男生都选择自己名单上排在首位的女生。
 88     for(int i=1;i<=n;i++) ChoosePartener(S,i);
 89 
 90     while(S.size()!=0)
 91     {
 92         int manPos=S.top();S.pop();
 93         ChoosePartener(S,manPos);
 94     }
 95 }
 96 
 97 int main()
 98 {
 99     //freopen("data.in","r",stdin);
100     //freopen("data.out","w",stdout);
101     //clock_t st=clock();
102     int T;scanf("%d",&T);
103     while(T--)
104     {
105         scanf("%d",&n);char c;
106         man.clear();woman.clear();turn.clear();
107         for(int i=1;i<=n;i++)
108         {
109             getchar();scanf("%c",&c);
110             man[c]=i;temp[i]=c;
111         }
112         for(int i=1;i<=n;i++)
113         {
114             getchar();scanf("%c",&c);
115             woman[c]=i;turn[i]=c;
116         }
117         for(int i=1;i<=n;i++)
118         {
119             getchar();
120             scanf("%c:",&c);int t=man[c];
121             for(int j=0;j<n;j++)
122             {
123                 scanf("%c",&c);
124                 a[t][j]=woman[c];
125             }
126         }
127         for(int i=1;i<=n;i++)
128         {
129             getchar();
130             scanf("%c:",&c);int t=woman[c];
131             for(int j=0;j<n;j++)
132             {
133                 scanf("%c",&c);
134                 b[t][j]=man[c];
135             }
136         }
137         solve();
138         sort(temp+1,temp+1+n);
139         for(int i=1;i<=n;i++)
140         {
141             printf("%c %c
",temp[i],turn[ans[man[temp[i]]]]);
142         }
143         if(T!=0) printf("
");
144     }
145     //clock_t ed=clock();
146     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
147     return 0;
148 }