{"problem":{"name":"[NERC 2018]  Bimatching","description":{"content":"你与一些好友一起举办了一个舞会！ 在这个舞会上，有 $n$ 位男性和 $m$ 位女性，本来舞蹈的形式是一男一女跳的，但是由于男性紧缺，你并不能让所有女性都有一个男性舞伴，于是你发明了一种新的舞蹈形式：一个男性，搭配两个女舞伴。 当然，每个女性在挑选舞伴时，都会对那些男性舞伴做出评价，如果评价是 $1$，说明这位女性愿意和这位男性一起跳舞，只有当两位女性都愿意和那位男性跳舞时，才能成为一对舞伴。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1300,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9792"},"statements":[{"statement_type":"Markdown","content":"你与一些好友一起举办了一个舞会！\n\n在这个舞会上，有 $n$ 位男性和 $m$ 位女性，本来舞蹈的形式是一男一女跳的，但是由于男性紧缺，你并不能让所有女性都有一个男性舞伴，于是你发明了一种新的舞蹈形式：一个男性，搭配两个女舞伴。\n\n当然，每个女性在挑选舞伴时，都会对那些男性舞伴做出评价，如果评价是 $1$，说明这位女性愿意和这位男性一起跳舞，只有当两位女性都愿意和那位男性跳舞时，才能成为一对舞伴。\n\n你作为一个组织者，自然要为大家着想，你需要求出能凑出的最多的舞伴对数，**每个舞伴不能重叠**。\n\n## Input\n\n第一行一个数 $t (1 \\leq t \\leq 20)$，表示数据组数。\n\n接下来 $t$ 组数据，每组第一行两个整数 $n$ 和 $m$，此处我们保证 $1 \\leq n,m$ 且 $n + m \\leq 150$。\n\n然后一个 $n \\times m$ 的矩阵，$a_{i,j}$ 表示 $j$ 号女士是否愿意和 $i$ 号男士一起跳舞。\n\n## Output\n\n对于每组测试数据，输出一行，表示最多能凑出的舞伴对数。\n\n[samples]\n\n## Background\n\n翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) B 题。\n\n## Note\n\n数据保证 $1 \\leq t \\leq 20$，$1 \\leq n, m$ 且 $n + m \\leq 150$。\n\n下图是对样例一和样例二的解释，其中加粗部分表示其中的一种可行方案。\n\n样例一：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9dfwv4dr.png)\n\n样例二：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/woscpjcn.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9792","tags":["2018","ICPC","NERC/NEERC"],"sample_group":[["2\n2 3\n111\n111\n3 4\n0110\n1100\n0011","1\n2"],["1\n3 6\n001100\n111111\n001100","2"]],"created_at":"2026-03-03 11:09:25"}}