看menci的博客点出二分的思路然后做出来，menci太强辣
原题：
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
N<=50 K<=30
看榜上的都是0MS，这是什么神奇的做法
先看menci的博客发现这道题，知道是网络流，想了一段时间无果，回menci的博客看了一眼，然后发现两个字
"二分"
然后思路就想出来了，二分答案，根据答案建图然后验证是否能跑到满流
具体建图方法就很简答了，相互喜欢的男女权值为1，每个男女要额外一个点来保证和不喜欢的人的限制，本来的点和额外的点中间权值为k，两个不喜欢的男女之间额外的点权值为1，源到男，女到汇权值为二分的答案
如果能跑到满流就说明答案和法
另外有一点需要注意就是二分的下线要从0开始，因为可能会无解
二分也是转换问题很关键的方式，以后想题还要尽量考虑一下
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int oo=;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
struct ddd{int y,v,re;}; vector <ddd> e[];
inline void ist(int x,int y,int z){
e[x].push_back((ddd){y,z,e[y].size()});
e[y].push_back((ddd){x,,e[x].size()-});
}
int n,m; int s,t; int n2,n3,n4;
char a[][];
int lvl[];
int q[],hd=;
void clear(){ for(int i=s;i<=t;++i) e[i].clear();}
bool gtlvl(){
memset(lvl,,sizeof(lvl));
q[hd=]=s,lvl[s]=;
int x,sz;
for(int k=;k<=hd;++k){
x=q[k],sz=e[x].size();
for(int i=;i<sz;++i)if(e[x][i].v && !lvl[e[x][i].y])
lvl[e[x][i].y]=lvl[x]+,q[++hd]=e[x][i].y;
}
return lvl[t];
}
int agmt(int x,int y){
if(x==t) return y;
int mxflw=,flw,sz=e[x].size();
for(int i=;i<sz && mxflw<y;++i)if(lvl[e[x][i].y]==lvl[x]+ && e[x][i].v)
if(flw=agmt(e[x][i].y,min(y-mxflw,e[x][i].v))){
mxflw+=flw;
e[x][i].v-=flw,e[e[x][i].y][e[x][i].re].v+=flw;
}
if(!mxflw) lvl[x]=;
return mxflw;
}
int dnc(){
int bwl=,flw;
while(gtlvl())while(flw=agmt(s,oo)) bwl+=flw;
return bwl;
}
bool chck(int x){
clear();
for(int i=;i<=n;++i){
for(int j=;j<=n;++j){
if(a[i][j]=='Y') ist(i,j+n3,);
else ist(i+n,j+n2,);
}
ist(i,i+n,m),ist(i+n2,i+n3,m);
ist(s,i,x),ist(i+n3,t,x);
}
return dnc()==x*n;
}
int bnrsch(){
int l=,r=n,md;
while(l+<r){ md=(l+r)>>; (chck(md)?l:r)=md;}
return chck(r)?r:l;
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n>>m; n2=n*,n3=n*,n4=n*; s=,t=n4+;
/*for(int i=1;i<=n;++i){
scanf("%s",s+1);
for(int j=1;j<=n;++j){
if(s[j]=='Y') ist(i,j+3n,1);
else ist(i+n,j+2n,1);
}
ist(i,i+n,k),ist(i+2n,i+3n,k);*/
for(int i=;i<=n;++i) scanf("%s",a[i]+);
cout<<bnrsch()<<endl;
return ;
}