{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eYou have just been hired by Amalgamated, Inc.\u0026nbsp;in the\n country of Acmania to oversee the transportation of raw\n materials to the company’s factories. Each supplier of raw\n materials and each factory resides in one of Acmania’s states.\n No state has both a factory and a supplier (and never more than\n one of either) and there are arcane laws governing which\n transportation companies can transport materials across state\n lines. Because of the fierce competition between factories and\n between suppliers each transportation company handles the\n output of at most one raw material site and delivers to at most\n one factory (or to another transportation company). Each\n supplier can produce enough material to contract with at most\n one factory and no factory will contract with more than one\n supplier. Your job is to determine the maximum number of\n factories that can be supplied with raw materials.\u003c/p\u003e\n\n \u003cp\u003eFor example, suppose that there are three suppliers in\n states A, B and C, and three factories in states D, E and F.\n Let’s say you contract three transportation firms: firm\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e can transport between\n states A, E and G; firm \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e can transport between states A, C\n and E; and firm \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e can\n transport between states B, D and F. In this case, you can\n supply at most two factories (for example, factory E can be\n supplied from supplier A using firm \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, and factory F can be supplied\n from supplier B using firm \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e). If you find a fourth firm that\n transports between states G and F then you can supply all three\n factories: factory D can be supplied from B using firm\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e, factory E can be\n supplied from C using firm \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e, and factory F can be supplied\n from A using firms \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input will start with four positive integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e indicating the number of states,\n raw material sites, factories and transportation companies,\n where \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq r,f \\leq\n 200$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$r+f \\leq s \\leq\n 600$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq t \\leq\n 1000$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eNext will follow a line containing \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e state names, one for each raw\n material site.\u003c/p\u003e\n\n \u003cp\u003eThe next line will contain \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e state names, one for each factory\n site.\u003c/p\u003e\n\n \u003cp\u003eFinally there will be \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e lines, one for each transportation\n company. Each of these lines will start with an integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq s$\u003c/span\u003e, indicating the\n number of states the company is allowed to work in, followed by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e state names. No state\n will contain both a raw material site and a factory site.\u003c/p\u003e\n\n \u003cp\u003eAll state names will be alphabetic strings with no\n blanks.\u003cbr\u003e\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the maximum number of factories that can be supplied\n with raw materials.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 3 3 3\nA B C\nD E F\n3 A E G\n3 A C E\n3 B D F\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 3 3 4\nA B C\nD E F\n3 A E G\n3 A C E\n3 B D F\n2 G F\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}