首页 > 代码库 > Marriage is Stable
Marriage is Stable
Marriage is Stable |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 64 Accepted Submission(s): 43 |
Problem Description Albert, Brad, Chuck are happy bachelors who are in love with Laura, Marcy, Nancy. They all have three choices. But in fact, they do have some preference in mind. Say Albert, he likes Laura best, but that doesn‘t necesarily mean Laura likes him. Laura likes Chuck more than Albert. So if Albert can‘t marry Laura, he thinks Nancy a sensible choice. For Albert, he orders the girls Laura > Nancy > Marcy. For the boys: Albert: Laura > Nancy > Marcy Brad: Marcy > Nancy > Laura Chuck: Laura > Marcy > Nancy For the girls: Laura: Chuck > Albert > Brad Marcy: Albert > Chuck > Brad Nancy: Brad > Albert > Chuck But if they were matched randomly, such as Albert <-> Laura Brad <-> Marcy Chuck <-> Nancy they would soon discover it‘s not a nice solution. For Laura, she likes Chuck instead of Albert. And what‘s more, Chuck likes Laura better than Nancy. So Laura and Chuck are likely to come together, leaving poor Albert and Nancy. Now it‘s your turn to find a stable marriage. A stable marriage means for any boy G and girl M, with their choice m[G] and m[M], it will not happen that rank(G, M) < rank(G, m[G]）and rank(M, G) < rank(M, m[M]). |
Input Each case starts with an integer n (1 <= n <= 500), the number of matches to make. The following n lines contain n + 1 names each, the first being name of the boy, and rest being the rank of the girls. The following n lines are the same information for the girls. Process to the end of file. |
Output If there is a stable marriage, print n lines with two names on each line. You can choose any one if there are multiple solution. Print "Impossible" otherwise. Print a blank line after each test. |
Sample Input 3Albert Laura Nancy MarcyBrad Marcy Nancy LauraChuck Laura Marcy NancyLaura Chuck Albert BradMarcy Albert Chuck BradNancy Brad Albert Chuck |
Sample Output Albert NancyBrad MarcyChuck Laura |
Author CHENG, Long |
Source ZOJ |
Recommend 8600 |
/*题意：给你n个男生暗恋的对象，n个女生暗恋的对象，如果刚好能组成n对不重复的情侣，就输出，如果不可能的话，就输出Impossible初步思路：很典型的二分匹配问题*/#include<bits/stdc++.h>using namespace std;/***********************二分匹配模板**************************/const int MAXN=1000;int g[MAXN][MAXN];//编号是0~n-1的 int linker[MAXN];//记录匹配点i的匹配点是谁bool used[MAXN];map<string,int> m;map<int ,string> M;int len=3;int n;string bname,gname;bool dfs(int u)//回溯看能不能通过分手来进行匹配{ int v; for(v=0;v<n*2;v++) if(g[u][v]&&!used[v]) //如果有这条边，并且这条边没有用过 { used[v]=true; if(linker[v]==-1||dfs(linker[v]))//如果这个点没有匹配过，并且能找到匹配点，那么就可以以这个边作为匹配点 { linker[v]=u; return true; } } return false; } int hungary()//返回最大匹配数{ int res=0; int u; memset(linker,-1,sizeof(linker)); for(u=0;u<n*2;u++) { memset(used,0,sizeof(used)); if(dfs(u))//如果这个点有匹配点 res++; } return res; }/***********************二分匹配模板**************************/void init(){ len=2; memset(g,0,sizeof g);}int main(){ // freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF){ init(); for(int i=0;i<n;i++){ cin>>bname; m[bname]=i; M[i]=bname; for(int j=0;j<n;j++){ cin>>gname; if(m.find(gname)==m.end()){ m[gname]=++len; M[len]=gname; } g[m[bname]][m[gname]]=1; } } // for(int i=0;i<n*2;i++){ // cout<<M[i]<<" "; // }cout<<endl; for(int i=0;i<n;i++){ cin>>gname; for(int j=0;j<n;j++){ cin>>bname; g[m[gname]][m[bname]]=1; } } // for(int i=0;i<n*2;i++){ // for(int j=0;j<n*2;j++){ // cout<<g[i][j]<<" "; // }cout<<endl; // } //cout<<hungary()<<endl; if(hungary()==n*2){ for(int i=0;i<n;i++){ cout<<M[i]<<" "<<M[linker[i]]<<endl; } }else{ puts("Impossible"); } } return 0;}
Marriage is Stable
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。