F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛模拟题,有意者请联系本站邮箱Lydsy2012@163.com,欢迎各校教练、老师、家长来信咨询,非诚勿扰。
Problem 1305. -- [CQOI2009]dance跳舞

1305: [CQOI2009]dance跳舞

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 4465  Solved: 1943
[Submit][Status][Discuss]

Description

一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

Input

第一行包含两个整数n和k。以下n行每行包含n个字符,其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数,即舞曲数目的最大值。

Sample Input

3 0
YYY
YYY
YYY

Sample Output

3

HINT

N<=50 K<=30

Source

加强数据By dwellings and liyizhen2

[Submit][Status][Discuss]

HOME Back