Description
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
Input
第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。
Output
仅一个数，即舞曲数目的最大值。
Sample Input
3 0
YYY
YYY
YYY
YYY
YYY
YYY
Sample Output
3
HINT
N<=50 K<=30
把男孩女孩都拆点为x,y
S向x连边，容量为a，y向汇点连边，容量为a
a可以二分，可以枚举（反正只有30）
男生x-->y连边为k，女生y-->x连边为k，男生喜欢女生在左部连边，反之在右部
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int inf=,N=;
struct ee{int to,next,f;}e[];
int head[N],q[N*],dis[N],map[N][N];
int S,T,n,m,cnt=,ans,w,k,mx; void ins(int u,int v,int f){
e[++cnt].to=v;e[cnt].f=f;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].f=;e[cnt].next=head[v];head[v]=cnt;
} bool bfs(){
for (int i=;i<=T;i++) dis[i]=inf;
int h=,t=,now;
q[]=S;dis[S]=;
while(h!=t){
now=q[++h];
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[now]+<dis[v]){
dis[v]=dis[now]+;
if (v==T)return ;
q[++t]=v;
}
}
}
if (dis[T]==inf) return ; return ;
} int dinic(int now,int f){
if (now==T) return f;
int rest=f;
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[v]==dis[now]+&&rest){
int t=dinic(v,min(rest,e[i].f));
if (!t) dis[v]=;
e[i].f-=t;
e[i^].f+=t;
rest-=t;
}
}
return f-rest;
}
void build(int f){
cnt=;
memset(head,,sizeof(head));
for(int i=;i<=n;i++) ins(S,i,f);
for(int i=n+;i<=*n;i++) ins(i,T,f);
for(int i=;i<=n;i++) ins(i,i+*n,k);
for(int i=n+;i<=*n;i++) ins(i+*n,i,k);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(map[i][j]) ins(i,j+n,);
else ins(i+*n,j+*n,);
}
}
int main(){
scanf("%d%d",&n,&k);
T=*n+;
char s[];
for(int i=;i<=n;i++){
scanf("%s",s+);
for(int j=;j<=n;j++)
if(s[j]=='Y') map[i][j]=;
}
int l=,r=;
while(l<=r)
{
int mid=(l+r)>>;
build(mid);
ans=;while(bfs()) ans+=dinic(S,inf);
if(ans>=n*mid){mx=mid;l=mid+;}
else r=mid-;
}
printf("%d",mx);
}