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和i'，女的为j和j'
假设我们二分的答案为p
那么从s向所有的i连容量为p的边，从所有的j向t连容量为p的边
喜欢的男女对应的i向j连容量为1的边，不喜欢的男女对应的i向j连容量为1的边
所有的男的i向i'连容量为k的边，所有女的j'向j连容量为k的边
如果可行，那么最大流为p*n
上述算法的正确性基于以下定理：
若二分图中，X部中点度数全为t，Y部中点度数全为t，那么该图定存在t个完全不同的完备匹配。
用归纳法易证。
t=1时一定是对的，当t>1时，直接去掉一个匹配，就变成了t-1的问题了
现在我们就是要证明的是，t>0时一定存在一个匹配，当t=1时，有唯一的匹配，当t>1时，显然至少有一个匹配（我不知道怎么严格的证明......有的话留言给我吧，谢谢）
网上还看见有贪心的做法，我觉得不对，我也写了一个贪心的做法，WA了，估计是因为贪心不对，所以BZOJ加强了数据吧
我觉得贪心不对是因为这个
我们一开始给了无限大的流量（喜欢的为无限大，不喜欢的为k），然后取最小值，但是这样流量参差不齐，我们在减少那些大的流量时，可能会把这些小的流量变得更小（我自己瞎想的，勿喷）
const
maxn=;
inf=;
var
map:array[..maxn*,..maxn*]of longint;
a:array[..maxn,..maxn]of char;
n,k,s,t,l,r,mid:longint; procedure init;
var
i,j:longint;
begin
readln(n,k);
s:=;
t:=*n+;
for i:= to n do
begin
for j:= to n do
read(a[i,j]);
readln;
end;
end; var
his,dis,vh,pre:array[..maxn*]of longint;
min,aug,flow:longint;
flag:boolean; function sap:boolean;
var
i,j:longint;
begin
fillchar(map,sizeof(map),);
fillchar(dis,sizeof(dis),);
fillchar(vh,sizeof(vh),);
flow:=;
for i:= to n do
for j:= to n do
if a[i,j]='Y' then map[*i,*j+*n]:=
else map[*i-,*j+*n-]:=;
for i:= to n do
begin
map[s,*i]:=mid;
map[*i+*n,t]:=mid;
map[*i,*i-]:=k;
map[*i+*n-,*i+*n]:=k;
end;
vh[]:=t+;
i:=s;
aug:=inf;
while dis[i]<=t do
begin
his[i]:=aug;
flag:=false;
for j:=s to t do
if (map[i,j]>) and (dis[i]=dis[j]+) then
begin
pre[j]:=i;
flag:=true;
if aug>map[i,j] then aug:=map[i,j];
i:=j;
if i=t then
begin
inc(flow,aug);
while i<>s do
begin
inc(map[i,pre[i]],aug);
dec(map[pre[i],i],aug);
i:=pre[i];
end;
aug:=inf;
end;
break;
end;
if flag then continue;
min:=t;
for j:=s to t do
if (map[i,j]>) and (min>dis[j]) then min:=dis[j];
dec(vh[dis[i]]);
if vh[dis[i]]= then break;
dis[i]:=min+;
inc(vh[dis[i]]);
if i<>s then
begin
i:=pre[i];
aug:=his[i];
end;
end;
exit(flow=mid*n);
end; begin
init;
l:=;
r:=n;
while l<>r do
begin
mid:=(l+r+)>>;
if sap then l:=mid
else r:=mid-;
end;
write(l);
end.