【bzoj1305】[CQOI2009]dance跳舞

2014年3月13日3,4700

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

题解

先把每个人i拆分成ix和iy两个节点,ix连向喜欢的人,iy连向不喜欢的人,容量为1(比如如果男生i与女生j互相喜欢,则由ix连向jx,如果男生i与女生j互相不喜欢,则由iy连向jy),再将每个男生男生ix连向iy,容量为k;每个女生iy连向ix,容量为k。由源点向每个男生的x节点连上一条边,再由每个女生的x节点向汇点连上一条边,容量均为a。最后从小到大枚举a,计算最大流flow,若发现a*n>flow(不满流),则停止枚举,a-1即为答案。

或者可以二分