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()
- {
- queueq;
- 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;
- }
- }
来源: http://www.bubuko.com/infodetail-3031343.html