Description:


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

Input:


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

Output:


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

Sample Input:


Sample Output:


题解:


网络流的题目都是这样,建模比较难想~~~
把每一个人拆成两个点x, y。
若男生接女生相互喜欢,男生的x连向女生的x;否则男生的y连向女生的y。边权为1。
对于每一个男生,x连向y,对于每一个女生y连向x。边权为k。
源点向每一个男生的x点连一条边,每一个女生的x点向汇点连一条边。边权为ans。
枚举ans的值(当然二分也可以)。
直到不满流( \(ans \times n > flow\) ),退出,输出ans-1。

代码如下: