1239 - 跳舞 - acm.bjtu

1239. 跳舞

时间限制 1000 ms 内存限制 128 MB

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

输入数据

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

输出数据

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

样例输入

复制

Input 1:
3 0
YYY
YYY
YYY

Input 2:
3 0
YYY
YYN
YNY

Input 3:
2 0
YN
YN

Input 4:
2 1
YN
YN
     ·  \n
 · \n
   \n
   \n
   \n
\n
     ·  \n
 · \n
   \n
   \n
   \n
\n
     ·  \n
 · \n
  \n
  \n
\n
     ·  \n
 · \n
  \n
  \n

样例输出

复制

Output 1:
3

Output 2:
2

Output 3:
0

Output 4:
1
      ·  \n
 \n
\n
      ·  \n
 \n
\n
      ·  \n
 \n
\n
      ·  \n
 \n

样例说明

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

提交

请先登录

提交

Source

NOI2009重庆市代表队选拔赛第三题