题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1305
解题思路：
转自：https://blog.csdn.net/u012288458/article/details/50709571
二分答案
每个点拆成两个点x,x'
每个男生x向x'连一条容量为k的边
每个女生y'向y连一条容量为k的边
源点S向每个男生连一条容量为ans的边
每个女生向汇点T连一条容量为ans的边
对于男生x和女生y，
如果互相喜欢，则x向y连一条容量为1的边
如果不互相喜欢，则x’向y'连一条容量为1的边
若最大流为n*ans则可行，否则不可行
点数4n+2
边数(4n+n^2)*2
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define LL long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define bug cout<<"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"<<endl;
#define bugc(_) cout << (#_) << " = " << (_) << endl;
using namespace std;
const int N=5e2+;
const int M=5e3+;
const int INF=0x3f3f3f3f; struct node{
int to,next,flow;
}edge[M*]; int cnt,st,en,n,k;
int head[N],dep[N],like[N][N]; void init(){
cnt=;
memset(head,,sizeof(head));
} void link(int u,int v,int flow){
edge[cnt]=node{v,head[u],flow};
head[u]=cnt++;
edge[cnt]=node{u,head[v],};
head[v]=cnt++;
} int bfs(){
memset(dep,,sizeof(dep));
dep[st]=;
queue<int>q;
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=edge[i].next){
node t=edge[i];
if(t.flow&&!dep[t.to]){
dep[t.to]=dep[u]+;
q.push(t.to);
}
}
}
return dep[en];
} int dfs(int u,int fl){
if(u==en) return fl;
for(int i=head[u];i;i=edge[i].next){
node &t=edge[i];
if(t.flow&&dep[u]+==dep[t.to]){
int x=dfs(t.to,min(t.flow,fl));
if(x>){
t.flow-=x;
edge[i^].flow+=x;
return x;
}
}
}
dep[u]=-;
return ;
} int dinic(){
int ans=;
while(bfs()){
while(int d=dfs(st,INF)){
ans+=d;
}
}
return ans;
} void build(int mid){
init();
for(int i=;i<=n;i++){
link(st,i,mid);
link(i,i+n,k);
link(i+*n,en,mid);
link(i+*n,i+*n,k);
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(like[i][j])
link(i,j+*n,);
else
link(i+n,j+*n,);
}
}
} int main(){
while(~scanf("%d%d",&n,&k)){
for(int i=;i<=n;i++){
char tmp[];
scanf("%s",tmp+);
for(int j=;j<=n;j++){
if(tmp[j]=='Y')
like[i][j]=;
}
}
st=,en=*n+;
int l=,r=n,ans=-;
while(l<=r){
int mid=(l+r)/;
build(mid);
int sum=dinic();
if(sum>=n*mid){
ans=mid;
l=mid+;
}
else
r=mid-;
}
printf("%d\n",ans);
}
return ;
}