{"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 \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/c6e729d65d80c104b2e084d7f08b0f49?v\u003d1715974332\" alt\u003d\"/problems/crowdcontrol/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eThe BAPC draws a large number of visitors to Amsterdam. Many\n of these people arrive at the train station, then walk from\n intersection to intersection through the streets of Amsterdam\n in a big parade until they reach the BAPC location.\u003c/p\u003e\n\n \u003cp\u003eA street can only allow a certain number of people per hour\n to pass through. This is called the \u003cem\u003ecapacity\u003c/em\u003e of the\n street. The number of people going through a street must never\n exceed its capacity, otherwise accidents will happen. People\n may walk through a street in either direction.\u003c/p\u003e\n\n \u003cp\u003eThe BAPC organizers want to prepare a single path from train\n station to BAPC location. They choose the path with maximum\n capacity, where the capacity of a path is defined to be the\n minimum capacity of any street on the path. To make sure that\n nobody walks the wrong way, the organizers close down the\n streets which are incident\u003ca href\u003d\"https://open.kattis.com/problems/crowdcontrol#a0000000005\" class\u003d\"footnote\"\u003e\u003csup class\u003d\"footnotemark\"\u003e1\u003c/sup\u003e\u003c/a\u003e to an\n intersection on the path, but not part of the path.\u003c/p\u003e\n\n \u003cp\u003eCan you write a program to help the organizers decide which\n streets to block? Given a graph of the streets and\n intersections of Amsterdam, produce the list of streets that\n need to be closed down in order to create a single\n maximum-capacity path from the train station to the BAPC. The\n path must be simple, i.e.\u0026nbsp;it may not visit any\n intersection more than once.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe first line contains two integers: \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, the number of intersections\n in the city, and \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e,\n the number of streets (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n n,m \\le 1000$\u003c/span\u003e).\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eThe following \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines each specify a single street. A street is specified\n by three integers, \u003cspan class\u003d\"tex2jax_process\"\u003e$a_\n i$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$b_ i$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c_ i$\u003c/span\u003e, where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b_ i$\u003c/span\u003e are ids of the\n two \u003cem\u003eintersections\u003c/em\u003e that are connected by this\n street (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le a_ i, b_ i\n \u0026lt; n$\u003c/span\u003e) and \u003cspan class\u003d\"tex2jax_process\"\u003e$c_\n i$\u003c/span\u003e is the capacity of this street (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le c_ i \\le 500000$\u003c/span\u003e). Streets\n are numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e\n to \u003cspan class\u003d\"tex2jax_process\"\u003e$m-1$\u003c/span\u003e in the given\n order.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eYou may assume the following:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eAll visitors start walking at the train station which is\n the intersection with id \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e. The BAPC is located at the\n intersection with id \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eThe intersections and streets form a connected\n graph.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eNo two streets connect the same pair of\n intersections.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eNo street leads back to the same intersection on both\n ends.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eThere is a unique simple path of maximum capacity.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput a single line containing a list of space separated\n street numbers that need to be blocked in order to create a\n single maximum-capacity path from train station to BAPC. Sort\n these street numbers in increasing order.\u003c/p\u003e\n\n \u003cp\u003eIf no street must be blocked, output the word ā\u003ctt class\u003d\"ttfamily\"\u003enone\u003c/tt\u003eā instead.\u003c/p\u003e\n\n \u003cdiv id\u003d\"a0000000006\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/ed01847f3860fc3515282584d6d6c312?v\u003d1715974332\" alt\u003d\"\\includegraphics[width\u003d0.95\\textwidth ]{image.pdf}\" style\u003d\"width:95.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of the first example input.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\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 10\n0 1 800\n1 2 300\n2 3 75\n3 4 80\n4 5 50\n4 6 100\n6 1 35\n0 6 10\n0 2 120\n0 3 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 2 4 6 7 8\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\u003e4 4\n0 1 10\n1 2 50\n0 3 30\n1 3 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 3\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 3\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\u003e4 3\n0 1 10\n1 2 20\n2 3 30\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003enone\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}