{"problem":{"name":"「SvR-2」1+2=3","description":{"content":"你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $0,1,2$，你要将所有木棒拼起来，使相邻的数和为 $3$ 的对数最大。 例如，$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒，如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\\text{ - }\\textcolor{red}{\\unde","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9088"},"statements":[{"statement_type":"Markdown","content":"你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $0,1,2$，你要将所有木棒拼起来，使相邻的数和为 $3$ 的对数最大。\n\n例如，$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒，如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\\text{ - }\\textcolor{red}{\\underline{\\textbf 2}},\\textcolor{red}{\\underline{\\textbf 1}}\\text{ - }0$ 这样拼相邻的数和为 $3$ 的对数是 $1$，因为 $2+1=3$。\n\n## Input\n\n**本题有多组数据。**\n\n输入的第一行一个正整数表示数据组数 $T$。\n\n对于每组数据，一行 $9$ 个非负整数，分别表示 $0\\text{ - }0,0\\text{ - }1,0\\text{ - }2,1\\text{ - }0,1\\text{ - }1,1\\text{ - }2,2\\text{ - }0,2\\text{ - }1,2\\text{ - }2$ 型木棒的个数。\n\n## Output\n\n$T$ 行，每行一个整数表示答案。\n\n[samples]\n\n## Note\n\n#### 数据规模与约定\n\n对于全部数据，保证 $1\\le T\\le 10^5$，记 $a_{i,j}$ 表示 $i\\text-j$ 木棒的个数，保证 $0\\le a_{i,j}\\le 10^9$。\n\n**本题自动开启捆绑测试和 O2 优化。**\n\n记 $sum$ 表示一个测试点中所有数据的所有 $a_{i,j}$ 之和。\n\n| Subtask | $T$ | $sum$ | 特殊性质 |分值 |\n| :------: | :------: | :------: | :------: | :------: |\n| $1$ | $1 \\leq T \\leq 10$ | $1\\le sum\\le 10$ |无| $10 \\operatorname{pts}$ |\n| $2$ | $1 \\leq T \\leq 50$ | $1\\le sum\\le 80$ | 无|$20 \\operatorname{pts}$ |\n| $3$ | 无特殊限制 | 无特殊限制 |A| $15\\operatorname{pts}$ |\n| $4$ | 无特殊限制 | 无特殊限制 |B| $20 \\operatorname{pts}$ |\n| $5$ | $1\\le T\\le 1000$ | 无特殊限制 |C| $20 \\operatorname{pts}$ |\n| $6$ | 无特殊限制 | 无特殊限制 |无| $15 \\operatorname{pts}$ |\n\n特殊性质 A：$a_{i,j}$ 在 $[0,10^9]$ 中均匀随机生成。\n\n特殊性质 B：所有 $a_{i,j}>0$。\n\n特殊性质 C：所有 $a_{i,j}\\le 100$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9088","tags":["贪心","2023","网络流","洛谷原创","O2优化","图论建模","欧拉回路","费用流","洛谷月赛","Ad-hoc"],"sample_group":[["3\n4 1 3 4 7 7 9 10 3\n6 3 6 4 3 4 5 6 6\n6 10 7 1 4 2 6 4 2\n","31\n23\n19\n"]],"created_at":"2026-03-03 11:09:25"}}