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
Source
加强数据By dwellings and liyizhen2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
最大流+二分答案+拆点~
对于每一个人，拆成喜欢和不喜欢分别建图，从源点向所有喜欢的男生点连边，再从所有喜欢的男生点向对应的不喜欢的男生点连边；从所有喜欢的女生点向汇点连边，再从所有不喜欢的女生点向对应的喜欢的女生点连边，最后从喜欢的男生点向对应的喜欢的女生点连边，再从不喜欢的男生点向对应不喜欢的女生点连边。
（如果看不懂上面一段像绕口令一样的话，就直接看代码吧……原谅我的语言表达能力太差……）
但是我们限制流入量要用到答案，怎么办呢，就二分答案，每次建图。
实际上还挺快的，我的程序64ms~
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define inf 999999999int n,k,fi[202],w[12001],ne[12001],v[12001],cnt,dis[202],tot,ans;
char s[51][51];void add(int u,int vv,int val)
{w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;w[++cnt]=u;ne[cnt]=fi[vv];fi[vv]=cnt;v[cnt]=0;
}bool bfs()
{queue<int> q;memset(dis,-1,sizeof(dis));q.push(0);dis[0]=0;while(!q.empty()){int k=q.front();q.pop();for(int i=fi[k];i;i=ne[i])if(v[i] && dis[w[i]]==-1){dis[w[i]]=dis[k]+1;q.push(w[i]);}}if(dis[tot]==-1) return 0;return 1;
}int findd(int u,int vv)
{if(u==tot) return vv;int kkz,now=0;for(int i=fi[u];i;i=ne[i])if(v[i]>0 && dis[w[i]]==dis[u]+1 && (kkz=findd(w[i],min(v[i],vv-now)))){v[i]-=kkz;v[i^1]+=kkz;now+=kkz;if(now==vv) return now;}if(!now) dis[u]=-1;return now;
}bool cal(int u)
{int totans=0;cnt=1;memset(fi,0,sizeof(fi));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(s[i][j]=='Y') add(i,j+n,1);else add(i+2*n,j+3*n,1);add(0,i,u);add(i,i+2*n,k);add(i+3*n,i+n,k),add(i+n,tot,u);}while(bfs()) totans+=findd(0,inf);if(totans>=u*n) return 1;return 0;
}int main()
{scanf("%d%d",&n,&k);tot=4*n+1;for(int i=1;i<=n;i++) scanf("%s",s[i]+1);int l=0,r=n;while(l<=r){int mid=(l+r)>>1;if(cal(mid)) l=mid+1,ans=mid;else r=mid-1;}printf("%d\n",ans);return 0;
}