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

可复制的 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