题目：BZOJ1305、洛谷P3153、Vijos P1521。
题目大意：有n个男生和n个女生，每个男生有一些喜欢的女生，男生喜欢的女生一定也喜欢男生。每个男生只愿意和不喜欢的女生跳k次舞（女生同），且如果两人已经一起跳过舞，那么不会再一起跳舞。每次跳舞需要n对男生n对女生。求最多能跳几次舞。
解题思路：二分+最大流。首先二分答案很容易想到（数据小估计枚举也行），然后就是最大流了，但男生和女生有喜欢和不喜欢的关系，如何建图呢？
我们把男生拆成x和y，女生也拆成x和y，且x和y间连一条容量为k的边，表示最多和k个不喜欢的人跳舞。那么如果这个男生喜欢女生，就把男生的x和女生的y连一条容量为1的边，如果不喜欢，就把男生的y和女生的x连一条容量为1的边。超级源点s往所有男生的x连一条容量为p的边（p为当前二分的答案），女生的y向超级汇点t连一条容量为p的边。如果能跳p次舞，那么最大流的答案一定是n*p，所以我们只要用这个作为判断条件即可。
此题主要难点在于建图。
以下为Dinic算法代码。
C++ Code：
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define min(a,b) (((a)<(b))?(a):(b))
struct edge{
int from,to,cap,rev;
};
vector<edge>G[300];
int n,k,level[300],iter[300];
char ch,w[55][55];
queue<int>q;
inline void addedge(int from,int to,int flow){
G[from].push_back((edge){from,to,flow,G[to].size()});
G[to].push_back((edge){to,from,0,G[from].size()-1});
}
void bfs(int s,int t){
memset(level,-1,sizeof level);
level[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<G[u].size();++i){
edge& e=G[u][i];
if(e.cap>0&&level[e.to]<0){
level[e.to]=level[u]+1;
q.push(e.to);
}
}
}
}
int dfs(int u,int t,int f){
if(u==t)return f;
for(int& i=iter[u];i<G[u].size();++i){
edge& e=G[u][i];
if(e.cap>0&&level[e.to]>level[u]){
int d=dfs(e.to,t,min(e.cap,f));
if(d){
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t){
int flow=0;
for(;;){
bfs(s,t);
if(level[t]<0)return flow;
memset(iter,0,sizeof iter);
int f;
while(f=dfs(s,t,inf))flow+=f;
}
}
bool ok(int p){
for(int i=0;i<300;++i)G[i].clear();
for(int i=1;i<=n;++i)addedge(0,i,p);
for(int i=1;i<=n;++i)addedge(i,i+n,k);
for(int i=n<<1|1;i<=(n<<1)+n;++i)addedge(i,i+n,k);
for(int i=n*3+1;i<=n<<2;++i)addedge(i,n<<2|1,p);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
if(w[i][j]=='Y'){
addedge(i,3*n+j,1);
}else{
addedge(i+n,j+(n<<1),1);
}
}
int d=max_flow(0,n<<2|1);
return d==p*n;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
ch=getchar();
while(ch!='Y'&&ch!='N')ch=getchar();
w[i][j]=ch;
}
}
int l=0,r=100,ans=0;
while(l<=r){
int mid=l+r>>1;
if(ok(mid))l=(ans=mid)+1;else
r=mid-1;
}
printf("%d
",ans);
return 0;
}