{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"给定 $n$ * $n$ 矩阵 $C_{i,j}$($1\\le i,j\\le n$),我们要找到满足以下条件的 $n$ * $n$ 的01矩阵 $X_{i,j}$($1\\le i,j\\le n$):\n\n1.$\\sum_{j\u003d2}^{n}X_{1,j}\u003d1$\n\n2.$\\sum_{i\u003d1}^{n-1}X_{i,n}\u003d1$\n\n3.对于每个 $i$($1\u003ci\u003cn$),满足$\\sum_{k\u003d1}^{n}X_{k,i}\u003d\\sum_{j\u003d1}^{n}X_{i,j}$。\n\n例如,如果 $n\u003d4$,我们可以得到以下等式:\n\n$X_{1,2}+X_{1,3}+X_{1,4}\u003d1$\n\n$X_{1,4}+X_{2,4}+X_{3,4}\u003d1$\n\n$X_{1,2}+X_{2,2}+X_{3,2}+X_{4,2}\u003dX_{2,1}+X_{2,2}+X_{2,3}+X_{2,4}$\n\n$X_{1,3}+X_{2,3}+X_{3,3}+X_{4,3}\u003dX_{3,1}+X_{3,2}+X_{3,3}+X_{3,4}$\n\n现在,我们想知道能达到的 $\\sum C_{i,j}\\times X_{i,j}$($1\\le i,j\\le n$)的最小值。"}},{"title":"输入格式","value":{"format":"MD","content":"输入包括多组测试点(不多于 35 个)。\n对于每个测试点,第一行是一个整数 $n$ ($1\\le n \\le 300$)\n下面 $n$ 行每行 $n$ 个整数,描述了矩阵 $C$ 。其中第 $i$ 行的第 $j$ 个数是 $C_{i,j}$ ($0\\le C_{i,j}\\le 100000$)"}},{"title":"输出格式","value":{"format":"MD","content":"对于每个测试点,输出能达到的 $\\sum C_{i,j}\\times X_{i,j}$($1\\le i,j\\le n$)的最小值。"}},{"title":"样例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e\u003cpre\u003e4\n1 2 4 10\n2 0 1 1\n2 2 0 5\n6 3 1 2\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"样例解释","value":{"format":"MD","content":"$X_{1,2}\u003dX_{2,4}\u003d1$,其余为 $0$。"}}]}