最大流。
首先二分答案，问题转化为x首舞曲是否可行。
考虑建图，对每个人建立三个点，分别表示全体，喜欢和不喜欢。
源点向每个男生全体点连一条容量为x的边。
每个男生整体点向喜欢点连一条容量为正无穷的边，向不喜欢点连一条容量为k的边。
每个男生喜欢点向所有他喜欢的女生的喜欢点连一条容量为一的边，不喜欢点向所有他不喜欢的女生的不喜欢点连一条容量为一的边。
每个女生喜欢点向整体点连一条容量为正无穷的边，不喜欢点向整体点连一条容量为k的边。
每个女生整体点向汇点连一条容量为x的边。
check即为判断最大流是否等于n*x。
本题中流量的定义为舞曲数，整体点向源汇点的连边保证了每一轮正好配成n对，如某一轮中存在一个女生对应多个男生，最终最大流就会减小。
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int dian=;
const int bian=;
const int INF=0x3f3f3f3f;
int n,k,tot;
int S,T;
int h[dian],nxt[bian],ver[bian],val[bian],ch[dian];
char map[][];
void add(int aa,int bb,int cc){
tot++;ver[tot]=bb;val[tot]=cc;nxt[tot]=h[aa];h[aa]=tot;
tot++;ver[tot]=aa;val[tot]=;nxt[tot]=h[bb];h[bb]=tot;
}
int bh(int aa,int p,int ok){
return (aa-)*+p+ok**n;
}
bool tell(){
memset(ch,-,sizeof(ch));
queue<int>q;
q.push(S);
ch[S]=;
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=h[t];i;i=nxt[i])
if(ch[ver[i]]==-&&val[i]){
q.push(ver[i]);
ch[ver[i]]=ch[t]+;
}
}
return ch[T]!=-;
}
int zeng(int a,int b){
if(a==T)
return b;
int r=;
for(int i=h[a];i&&b>r;i=nxt[i])
if(ch[ver[i]]==ch[a]+&&val[i]){
int t=zeng(ver[i],min(b-r,val[i]));
val[i]-=t,r+=t,val[i^]+=t;
}
if(!r)
ch[a]=-;
return r;
}
int dinic(){
int r=,t;
while(tell())
while(t=zeng(S,INF))
r+=t;
return r;
}
bool check(int mid){
memset(nxt,,sizeof(nxt));
memset(h,,sizeof(h));
tot=;
for(int i=;i<=n;i++){
add(S,bh(i,,),mid);
add(bh(i,,),T,mid);
add(bh(i,,),bh(i,,),INF);
add(bh(i,,),bh(i,,),k);
add(bh(i,,),bh(i,,),INF);
add(bh(i,,),bh(i,,),k);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(map[i][j]=='Y')
add(bh(i,,),bh(j,,),);
else
add(bh(i,,),bh(j,,),);
}
if(dinic()==n*mid)
return true;
return false;
}
int bin(int l,int r){
int mid;
while(l<r){
mid=(l+r+)>>;
if(check(mid))
l=mid;
else
r=mid-;
}
return l;
}
int main(){
scanf("%d%d",&n,&k);
S=*n+,T=*n+;
for(int i=;i<=n;i++)
scanf("%s",map[i]+);
printf("%d",bin(,));
return ;
}