题干：

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

Input

第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数，即舞曲数目的最大值。

Sample Input

3 0

YYY

YYY

YYY

Sample Output

3

Hint

N<=50 K<=30

解题报告：

  这题网络流，做法很多。可以直接二分可以跳多少支舞，然后网络流check一下。也可以每次每次的跑，直到第一次凑不满n个人为止。也可以每次给他一条流量为1的空间，让他凑n个人，然后再给他流量为1的空间，让他在残留网络上凑n个人，这样直到第一次凑不出n个人的时候break。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
int n,k,N;
int tot;
struct Edge {
	int to,ne,w;
} e[100005 * 2];
int head[10005];
int st,ed;
int dis[10050],q[10005];
void add(int u,int v,int w,int rw=0) {
	e[++tot].to=v;
	e[tot].w=w;
	e[tot].ne=head[u];
	head[u]=tot;
	e[++tot].to=u;
	e[tot].w=rw;
	e[tot].ne=head[v];
	head[v]=tot;	
}
bool bfs(int st,int ed) {
	memset(dis,-1,sizeof(dis));
	int front=0,tail=0;
	q[tail++]=st;
	dis[st]=0;
	while(front<tail) {
		int cur = q[front];
		if(cur == ed) return 1;
		front++;
		for(int i = head[cur]; i!=-1; i = e[i].ne) {
			if(e[i].w&&dis[e[i].to]<0) {
				q[tail++]=e[i].to;
				dis[e[i].to]=dis[cur]+1;
			}
		}
	}
	if(dis[ed]==-1) return 0;
	return 1;
}
int dfs(int cur,int limit) {//limit为源点到这个点的路径上的最小边权 
	if(limit==0||cur==ed) return limit;
	int w,flow=0;
	for(int i = head[cur]; i!=-1; i = e[i].ne) {		
		if(e[i].w&&dis[e[i].to]==dis[cur]+1) {
			w=dfs(e[i].to,min(limit,e[i].w));
			e[i].w-=w;
			e[i^1].w+=w;
			flow+=w;
			limit-=w;
			if(limit==0) break;
		}
	}
	if(!flow) dis[cur]=-1;
	return flow;
}
int dinic() {
	int ans = 0;
	while(bfs(st,ed)) 
		ans+=dfs(st,0x7fffffff);
	return ans;
}
char s[55][55];
int main() {
	cin>>n>>k;
	st=4*n+1,ed=st+1;
	N=ed+1;
	//init 
	tot=1;
	for(int i = 1; i<=N; i++) head[i] = -1;
	for(int i = 1; i<=n; i++) {
		scanf("%s",s[i]+1);
		add(i,i+n,k);add(i+2*n,i+3*n,k);		
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=n; j++) {
			if(s[i][j] == 'Y') add(i,j+3*n,1);
			else add(i+n,j+2*n,1);
		}
	}
	for(int ans = 0; ;ans++) {
		for(int i = 1; i<=n; i++) {
			add(st,i,1);add(3*n+i,ed,1);
		}
		if(dinic() != n) {
			printf("%d\n",ans);break;
		}				
	}			
	return 0;
}