{"id":293,"date":"2012-12-08T14:20:00","date_gmt":"2012-12-08T06:20:00","guid":{"rendered":"http:\/\/nike0good.jp1.rpvhost.net\/198"},"modified":"2012-12-08T14:20:00","modified_gmt":"2012-12-08T06:20:00","slug":"zoj_1576_stable_marriage_system_-_the_same_name","status":"publish","type":"post","link":"https:\/\/nike0good.com\/?p=293","title":{"rendered":"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d)"},"content":{"rendered":"
Marriage is Stable<\/span><\/div>\n
\n

Time Limit: <\/span>5 Seconds
\nMemory Limit: <\/span>32768 KB Special Judge<\/span> <\/center><\/p>\n
\n

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
\n 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.<\/p>\n

For the boys:<\/p>\n

Albert: Laura > Nancy > Marcy
\nBrad: Marcy > Nancy > Laura
\nChuck: Laura > Marcy > Nancy<\/p>\n

For the girls:<\/p>\n

Laura: Chuck > Albert > Brad
\nMarcy: Albert > Chuck > Brad
\nNancy: Brad > Albert > Chuck<\/p>\n

But if they were matched randomly, such as<\/p>\n

Albert <-> Laura
\nBrad <-> Marcy
\nChuck <-> Nancy<\/p>\n

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.<\/p>\n

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]\ufffd\ufffdand rank(M, G) < rank(M, m[M]).<\/p>\n

\nInput<\/strong><\/p>\n

Each case starts with an integer n (1 <= n <= 500), the number of matches to make.<\/p>\n

The following n lines contain n + 1 names each, the first being name of the boy, and rest being the rank of the girls.<\/p>\n

The following n lines are the same information for the girls.<\/p>\n

Process to the end of file.<\/p>\n

\nOutput<\/strong><\/p>\n

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.<\/p>\n

Print a blank line after each test.<\/p>\n

\nSample Input<\/strong><\/p>\n

3
\nAlbert Laura Nancy Marcy
\nBrad Marcy Nancy Laura
\nChuck Laura Marcy Nancy
\nLaura Chuck Albert Brad
\nMarcy Albert Chuck Brad
\nNancy Brad Albert Chuck<\/p>\n

\nSample Output<\/strong><\/p>\n

Albert Nancy
\nBrad Marcy
\nChuck Laura<\/p>\n

\n<\/p>\n

\u8fd9\u9898\u5c31\u662f\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf\uff0c<\/span><\/p>\n

\u6ce8\u610f\u6709\u540c\u540d\u7684\u7537\u5973\u3002<\/span><\/p>\n

<\/span><\/p>\n

#include<cstdio>\n#include<cstring>\n#include<cstdlib>\n#include<iostream>\n#include<functional>\n#include<algorithm>\n#include<queue>\n#include<iostream>\n#include<map>\n#include<string>\nusing namespace std;\n#define MAXN (2000+10)\nint n;\nqueue<int> q;\nmap<string,int> hpos_male,hpos_female;\n\nint female_like[MAXN][MAXN];  \/\/SIS\nint male_like[MAXN][MAXN];    \/\/SSI\nint match[MAXN];\nstring a[MAXN];\nint main()\n{\n\/\/\tfreopen("zoj1576.in","r",stdin);\n\twhile (scanf("%d",&n)!=EOF)\n\t{\n\t\thpos_male.clear();\n\t\thpos_female.clear();\n\t\tmemset(match,0,sizeof(match));\n\t\tint size=n+1;\n\t\tfor (int i=1;i<=n;i++)\n\t\t{\n\t\t\tcin>>a[i];hpos_male[a[i]]=i; q.push(i);\n\t\t\tfor (int j=1;j<=n;j++)\n\t\t\t{\n\t\t\t\tstring s;\n\t\t\t\tcin>>s;\n\t\t\t\tif (i==1)\n\t\t\t\t{\n\t\t\t\t\thpos_female[s]=size;\n\t\t\t\t\ta[size]=s;\n\t\t\t\t\tsize++;\n\t\t\t\t}\n\t\t\t\tmale_like[i][j]=hpos_female[s];\n\t\t\t}\n\t\t}\n\t\tfor (int i=n+1;i<=2*n;i++)\n\t\t{\n\t\t\tstring sg;\n\t\t\tcin>>sg;\n\t\t\tfor (int j=1;j<=n;j++)\n\t\t\t{\n\t\t\t\tstring s;\n\t\t\t\tcin>>s;\n\t\t\t\tfemale_like[hpos_female[sg]][hpos_male[s]]=j;\n\t\t\t}\n\t\t}\n\t\t\/*\n\t\tfor (int i=n+1;i<=2*n;i++)\n\t\t{\n\t\t\tfor (int j=1;j<=n;j++)\n\t\t\t\tcout<<female_like[make_pair(a[i],a[j])]<<' ';\n\t\t\tcout<<endl;\n\t\t}\n\t\t*\/\n\t\twhile (!q.empty())\n\t\t{\n\t\t\tint now=q.front();\n\t\t\tq.pop();\n\t\t\tfor (int j=1;j<=n;j++)\n\t\t\t{\n\t\t\t\tint v=male_like[now][j];\n\t\t\t\tif (!match[v])\n\t\t\t\t{\n\t\t\t\t\tmatch[now]=v;match[v]=now;\/\/cout<<now<<' '<<v<<endl;\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t\telse if (female_like[v][match[v]]>female_like[v][now])\n\t\t\t\t{\n\t\t\t\t\tq.push(match[v]);\n\t\t\t\t\tmatch[match[v]]=0;\n\t\t\t\t\tmatch[now]=v;match[v]=now;\/\/cout<<now<<' '<<v<<endl;\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tfor (int i=1;i<=n;i++)\n\t\t{\n\t\t\tcout<<a[i]<<' '<<a[match[i]]<<endl;\n\t\t}\n\t\tprintf("n");\n\t}\n\treturn 0;\n}<\/pre>\n<\/p>\n

\n<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"
Marriage is Stable Time Limit: 5 Seconds Memory Limit:  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","footnotes":""},"categories":[3],"tags":[105],"class_list":["post-293","post","type-post","status-publish","format-standard","hentry","category-defaultcategory","tag-stable_marriage_problem"],"yoast_head":"\nZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d) - nike0good<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/nike0good.com\/?p=293\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d) - nike0good\" \/>\n<meta property=\"og:description\" content=\"Marriage is Stable Time Limit: 5 Seconds Memory Limit: […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/nike0good.com\/?p=293\" \/>\n<meta property=\"og:site_name\" content=\"nike0good\" \/>\n<meta property=\"article:published_time\" content=\"2012-12-08T06:20:00+00:00\" \/>\n<meta name=\"author\" content=\"nike0good\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"nike0good\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=293#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=293\"},\"author\":{\"name\":\"nike0good\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\"},\"headline\":\"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d)\",\"datePublished\":\"2012-12-08T06:20:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=293\"},\"wordCount\":374,\"commentCount\":0,\"keywords\":[\"\u7a33\u5b9a\u5a5a\u59fb\u95ee\u9898\"],\"articleSection\":[\"DefaultCategory\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/nike0good.com\\\/?p=293#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=293\",\"url\":\"https:\\\/\\\/nike0good.com\\\/?p=293\",\"name\":\"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d) - nike0good\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/#website\"},\"datePublished\":\"2012-12-08T06:20:00+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=293#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/nike0good.com\\\/?p=293\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=293#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/nike0good.com\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d)\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#website\",\"url\":\"https:\\\/\\\/nike0good.com\\\/\",\"name\":\"nike0good\",\"description\":\"\u6709\u6240\u4f5c\u4e3a\u662f\u4eba\u751f\u7684\u6700\u9ad8\u5883\u754c\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/nike0good.com\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\",\"name\":\"nike0good\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"caption\":\"nike0good\"},\"sameAs\":[\"https:\\\/\\\/nike0good.com\"],\"url\":\"https:\\\/\\\/nike0good.com\\\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d) - nike0good","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/nike0good.com\/?p=293","og_locale":"zh_CN","og_type":"article","og_title":"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d) - nike0good","og_description":"Marriage is Stable Time Limit: 5 Seconds Memory Limit: […]","og_url":"https:\/\/nike0good.com\/?p=293","og_site_name":"nike0good","article_published_time":"2012-12-08T06:20:00+00:00","author":"nike0good","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"nike0good","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"4 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/nike0good.com\/?p=293#article","isPartOf":{"@id":"https:\/\/nike0good.com\/?p=293"},"author":{"name":"nike0good","@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad"},"headline":"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d)","datePublished":"2012-12-08T06:20:00+00:00","mainEntityOfPage":{"@id":"https:\/\/nike0good.com\/?p=293"},"wordCount":374,"commentCount":0,"keywords":["\u7a33\u5b9a\u5a5a\u59fb\u95ee\u9898"],"articleSection":["DefaultCategory"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/nike0good.com\/?p=293#respond"]}]},{"@type":"WebPage","@id":"https:\/\/nike0good.com\/?p=293","url":"https:\/\/nike0good.com\/?p=293","name":"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d) - nike0good","isPartOf":{"@id":"https:\/\/nike0good.com\/#website"},"datePublished":"2012-12-08T06:20:00+00:00","author":{"@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad"},"breadcrumb":{"@id":"https:\/\/nike0good.com\/?p=293#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/nike0good.com\/?p=293"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/nike0good.com\/?p=293#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/nike0good.com\/"},{"@type":"ListItem","position":2,"name":"ZOJ 1576(\u7a33\u5b9a\u5a5a\u59fb\u7cfb\u7edf-\u91cd\u540d)"}]},{"@type":"WebSite","@id":"https:\/\/nike0good.com\/#website","url":"https:\/\/nike0good.com\/","name":"nike0good","description":"\u6709\u6240\u4f5c\u4e3a\u662f\u4eba\u751f\u7684\u6700\u9ad8\u5883\u754c","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/nike0good.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad","name":"nike0good","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","caption":"nike0good"},"sameAs":["https:\/\/nike0good.com"],"url":"https:\/\/nike0good.com\/?author=1"}]}},"_links":{"self":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts\/293","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=293"}],"version-history":[{"count":0,"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts\/293\/revisions"}],"wp:attachment":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}