[CQOI2009]跳舞

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

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

输出格式
仅一个数，即舞曲数目的最大值。

输入输出样例
输入 #1复制
3 0
YYY
YYY
YYY

输出 #1复制
3

说明/提示
N<=50 K<=30

我们可以注意到，每一场跳舞都需要n对人，所以我们肯定不能直接跑最大流，因为可能有些人不能匹配，但是有些人能匹配多次。

所以我们需要二分场数。

怎么check呢？
比如我们当前二分的场数为mid，然后我们把人都拆点，分为喜欢和不喜欢，然后限制S到喜欢和不喜欢最大之和为mid，所以我们需要把喜欢和不喜欢的点连在一起，流量为k。

因为没有单向喜欢，所以喜欢的连一起，不喜欢的连一起。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e3+10,M=1e5+10;
int n,k,s,t,h[N],l,r;
int head[N],nex[M],to[M],w[M],tot;
char g[55][55];
inline void ade(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ade(a,b,c);	ade(b,a,0);}
inline int bfs(){
	queue<int> q;	q.push(s);	memset(h,0,sizeof h); h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f; int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
inline int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
inline int check(int mid){
	tot=1;	memset(head,0,sizeof head);
	for(int i=1;i<=n;i++)	
		add(s,i,mid),add(i,i+n,k),add(i+3*n,i+2*n,k),add(i+2*n,t,mid);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(g[i][j]=='Y')	add(i,j+2*n,1);
			else	add(i+n,j+3*n,1);
		}
	}
	return dinic()==n*mid;
}
signed main(){
	cin>>n>>k; l=0,r=n; t=n*4+1;
	for(int i=1;i<=n;i++)	scanf("%s",g[i]+1);
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid))	l=mid;
		else	r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}