HDU 1522 Marriage is Stable 稳定婚姻匹配

http://acm.hdu.edu.cn/showproblem.php?pid=1522

 

 

 

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define me(a,b) memset(a,b,sizeof(a))
#define N 552
typedef long long ll;
using namespace std;

int girl[N],boy[N],n,b[N][N],g[N][N];
bool vis[N][N];
string s,e;
map<string,int>bb,gg;
string bbb[N],ggg[N];

void init()
{
      me(girl,-1);
      me(boy,-1);
      me(vis,0);
      bb.clear();
      gg.clear();
}

void stable_march()
{
      queue<int>q;
      for(int i=0;i<n;i++)
            q.push(i);
      while(!q.empty())
      {
            int f=q.front();
            q.pop();
            for(int i=0;i<n;i++)
            {
                  int tmp=b[f][i];
                  if(vis[f][tmp])
                  {
                        continue;
                  }
                  vis[f][tmp]=1;
                  if(girl[tmp]==-1)
                  {
                        girl[tmp]=f;
                        boy[f]=tmp;
                        break;
                  }
                  else if(g[tmp][girl[tmp]]<g[tmp][f])
                  {
                        q.push(girl[tmp]);
                        girl[tmp]=f;
                        boy[f]=tmp;
                        break;
                  }
            }
      }
}

int main()
{
      //freopen("in.txt","r",stdin);
      while(cin>>n)
      {
            init();
            for(int i=0;i<n;i++)
            {
                  cin>>s;
                  bbb[i]=s;
                  bb[s]=i;
                  if(i==0)
                        for(int j=0;j<n;j++)
                        {
                              cin>>e;
                              b[i][j]=j;
                              gg[e]=j;
                              ggg[j]=e;
                        }
                  else
                        for(int j=0;j<n;j++)
                        {
                              cin>>e;
                              b[i][j]=gg[e];
                        }
            }
            for(int i=0;i<n;i++)
            {
                  cin>>s;
                  int t=gg[s];
                  for(int j=n-1;j>-1;j--)
                  {
                        cin>>e;
                        g[t][bb[e]]=j;
                  }
            }
            stable_march();
            for(int i=0;i<n;i++)
            {
                  cout<<bbb[i]<<' '<<ggg[boy[i]]<<endl;
            }
            cout<<endl;
      }
}