[NERC 2018] Bimatching

Luogu
IDLGP9792
Time1300ms
Memory512MB
DifficultyP6
2018ICPCNERC/NEERC
你与一些好友一起举办了一个舞会! 在这个舞会上,有 $n$ 位男性和 $m$ 位女性,本来舞蹈的形式是一男一女跳的,但是由于男性紧缺,你并不能让所有女性都有一个男性舞伴,于是你发明了一种新的舞蹈形式:一个男性,搭配两个女舞伴。 当然,每个女性在挑选舞伴时,都会对那些男性舞伴做出评价,如果评价是 $1$,说明这位女性愿意和这位男性一起跳舞,只有当两位女性都愿意和那位男性跳舞时,才能成为一对舞伴。 你作为一个组织者,自然要为大家着想,你需要求出能凑出的最多的舞伴对数,**每个舞伴不能重叠**。 ## Input 第一行一个数 $t (1 \leq t \leq 20)$,表示数据组数。 接下来 $t$ 组数据,每组第一行两个整数 $n$ 和 $m$,此处我们保证 $1 \leq n,m$ 且 $n + m \leq 150$。 然后一个 $n \times m$ 的矩阵,$a_{i,j}$ 表示 $j$ 号女士是否愿意和 $i$ 号男士一起跳舞。 ## Output 对于每组测试数据,输出一行,表示最多能凑出的舞伴对数。 [samples] ## Background 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) B 题。 ## Note 数据保证 $1 \leq t \leq 20$,$1 \leq n, m$ 且 $n + m \leq 150$。 下图是对样例一和样例二的解释,其中加粗部分表示其中的一种可行方案。 样例一: ![](https://cdn.luogu.com.cn/upload/image_hosting/9dfwv4dr.png) 样例二: ![](https://cdn.luogu.com.cn/upload/image_hosting/woscpjcn.png)
Samples
Input #1
2
2 3
111
111
3 4
0110
1100
0011
Output #1
1
2
Input #2
1
3 6
001100
111111
001100
Output #2
2
API Response (JSON)
{
  "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$,说明这位女性愿意和这位男性一起跳舞,只有当两位女性都愿意和那位男性跳舞时,才能成为一对舞伴。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments