← 返回题目列表

Codeforces · 1089/B

B. 双匹配

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Bimatching - 原题 PDF 第 1 页
原题PDF第2页
可复制的 PDF 提取文本
ICPC 2018 2019, NEERC   Northern Eurasia Finals, Online Mirror
                         St. Petersburg   Barnaul   Tbilisi   Almaty, December 2, 2018
Problem B. Bimatching

In the XIX Century dancing was one of the most important subjects learned by nobles at schools. Balls
were the main or even the only opportunity to get to know new people, both for romantic and for business
purposes. However, at that time many cavaliers died in wars. For these and other reasons, lack of cavaliers
for dances was a rather common issue at balls. But there was an elegant solution to this problem. Some
dances were modi ed for a cavalier to ask two ladies for a dance instead of one. New dances meant for a
set of triples appeared as well as usual dances for a set of pairs.

Nowadays there are communities interested in a reconstruction of dances, and the number of cavaliers is
still usually less than the number of ladies. So dances for lady-cavalier-lady triples are studied now, too.

Betty is a leader of a popular community of historical dances. Unfortunately, there are some pairs where
a cavalier and a lady dislike each other and do not want to dance together in the same triple. Betty
is rather observant and knows all such dislikes in the community. All she needs is a way to  nd the
maximum possible number t of triples that can be selected for a dance. She does not even need to know
such a bimatching between cavaliers and ladies, because she likes to puzzle dancers saying: And now form
t triples, please. I know that it is possible . Please help Betty to  nd the maximum lady-cavalier-lady
bimatching capacity.

Input

The  rst line of the input contains the number of test cases t (1 ≤t ≤20). Then t descriptions of test
cases follow.

For each test case the  rst line contains the number n of cavaliers and the number m of ladies (1 ≤n, m;
n + m ≤150). Next n lines contain strings of m zeros and ones each. The character at position ℓin row c
is one if and only if lady ℓcan be in one triple with cavalier c. The sum of n + m over all test cases in a
single input does not exceed 150.

Output

For each test case output the maximum number t of triples in a single line.

Examples

     standard input          standard output                 Illustration
 2                       1                                                                                     ℓ1     ℓ2     ℓ3
 2 3                     2
 111
 111
 3 4                                                                                 c1     c2
                                                                                 ℓ1     ℓ2     ℓ3     ℓ4 0110
 1100
 0011
                                                                                   c2     c1     c3

 1                       2                                                                            ℓ1    ℓ2    ℓ3    ℓ4    ℓ5    ℓ6
 3 6
 001100
 111111
 001100                                                                          c1    c2    c3

Note

In the illustration each line means that a cavalier can dance with a lady. Bold line means that a cavalier
asks a lady for a dance.




                                         Page 2 of 15