{"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\u003eThe administrators at Polygonal School want to increase\n enrollment, but they are unsure if their gym can support having\n more students. Unlike a normal, boring, rectangular gym, the\n gym floor at Polygonal is a regular \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e-sided polygon! They affectionately\n refer to the polygon as \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eThe coach has drawn several running paths on the floor of\n the gym. Each running path is a straight line segment\n connecting two distinct vertices of \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e. During gym class, the coach\n assigns each student a different running path, and the student\n then runs back and forth along their assigned path throughout\n the class period. The coach does not want students to collide,\n so each student’s path must not intersect any other student’s\n path. Two paths intersect if they share a common point\n (including an endpoint).\u003c/p\u003e\n \u003cp\u003eGiven a description of the running paths in \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e, compute the maximum number of\n students that can run in gym class simultaneously.\u003c/p\u003e\n \u003cdiv id\u003d\"img:runningroutes\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/1f1c1382a16236a245291d14e65da342?v\u003d1715788679\" alt\u003d\"\\includegraphics[width\u003d0.5\\textwidth ]{samples}\" style\u003d\"width:50.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustrations of the two sample inputs,\n with possible solutions highlighted in thick red lines.\n Solid black lines represent running paths that are not\n assigned to a student, and dashed black lines are used to\n show the boundary of \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e in places where no running\n path exists.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$3\n \\le n \\le 500$\u003c/span\u003e), the number of vertices in \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e. (The vertices are numbered in\n increasing order around \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e.) Then follows \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines of \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers each, representing a\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n \\times n$\u003c/span\u003e symmetric\n binary matrix which we’ll call \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j^{\\text {th}}$\u003c/span\u003e integer on the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i^{\\text {th}}$\u003c/span\u003e line\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M_{ij}$\u003c/span\u003e is \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e if a running path exists between\n vertices \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e of the polygon, and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e otherwise. It is\n guaranteed that for all \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n i,j \\le n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$M_{ij} \u003d\n M_{ji}$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$M_{ii}\u003d0$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003ePrint the maximum number of students that can be assigned to\n run simultaneously on the running paths, given the above\n constraints.\u003c/p\u003e\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\u003e3\n0 1 1\n1 0 1\n1 1 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\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\u003e6\n0 0 0 1 0 0\n0 0 0 0 1 1\n0 0 0 0 1 1\n1 0 0 0 0 0\n0 1 1 0 0 0\n0 1 1 0 0 0\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 "}}]}