/ Vijos / 题库 /

跳舞

跳舞

描述

一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。

有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。

给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

格式

输入格式

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

输出格式

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

样例1

样例输入1

3 0
YYY
YYY
YYY

样例输出1

3

样例2

样例输入2

3 0
YYY
YYN
YNY

样例输出2

2

样例3

样例输入3

2 0
YN
YN

样例输出3

0

样例4

样例输入4

2 1
YN
YN

样例输出4

1

限制

各个测试点1s

提示

对于30%的数据,n<=5,k<=2;
对于全部的数据,n<=50,k<=30;

来源

NOI'09浙江省选第一试第2题

信息

ID
1521
难度
5
分类
图结构 | 网络流 点击显示
标签
递交数
806
已通过
272
通过率
34%
上传者

相关

在下列训练计划中:

RP++分类题库