题目大意：给定n个男生和n个女生，一些互相喜欢而一些不。举行几次舞会，每次舞会要配成n对。不能有同样的组合出现。每一个人仅仅能与不喜欢的人跳k次舞，求最多举行几次舞会

将一个人拆成两个点。点1向点2连一条流量为k的边。两个人若互相喜欢则点1之间连边，不喜欢则点2之间连边

对于每个要验证的x值 将每个人的点1向源或汇连一条流量为x的边

然后二分答案跑最大流就可以

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 220

#define INF 0x3f3f3f3f

#define S 0

#define T (n<<2|1)

using namespace std;

struct abcd{

	int to,f,next;

}table[100100];

int head[M],tot=1;

int n,k;

char s[M];

int dpt[M];

bool BFS()

{

	static int q[M],r,h;

	int i;

	memset(dpt,-1,sizeof dpt);

	r=h=0;q[++r]=S;dpt[S]=1;

	while(r!=h)

	{

		int x=q[++h];

		for(i=head[x];i;i=table[i].next)

			if(table[i].f&&!~dpt[table[i].to])

			{

				dpt[table[i].to]=dpt[x]+1;

				q[++r]=table[i].to;

				if(table[i].to==T)

					return true;

			}

	}

	return false;

}

int Dinic(int x,int flow)

{

	int i,left=flow;

	if(x==T) return flow;

	for(i=head[x];i&&left;i=table[i].next)

		if(table[i].f&&dpt[table[i].to]==dpt[x]+1)

		{

			int temp=Dinic(table[i].to, min(left,table[i].f) );

			if(!temp) dpt[table[i].to]=-1;

			left-=temp;

			table[i].f-=temp;

			table[i^1].f+=temp;

		}

	return flow-left;

}

inline void Add(int x,int y,int z)

{

	table[++tot].to=y;

	table[tot].f=z;

	table[tot].next=head[x];

	head[x]=tot;

}

inline void Link(int x,int y,int z)

{

	Add(x,y,z);

	Add(y,x,0);

}

inline void Restore()

{

	int i;

	for(i=2;i<=tot;i+=2)

		table[i].f+=table[i^1].f,table[i^1].f=0;

}

bool Judge(int x)

{

	int i;

	Restore();

	for(i=tot-(n<<2)+1;i<=tot;i+=2)

		table[i].f=x;

	int ans=0;

	while( BFS() )

		ans+=Dinic(S,INF);

	return ans==n*x;

}

int Bisection()

{

	int l=0,r=n;

	while(l+1<r)

	{

		int mid=l+r>>1;

		if( Judge(mid) )

			l=mid;

		else

			r=mid;

	}

	if( Judge(r) )

		return r;

	return l;

}

int main()

{

	int i,j;

	cin>>n>>k;

	for(i=1;i<=n;i++)

	{

		Link(i,n+i,k);

		Link(n+n+i,n+n+n+i,k);

	}

	for(i=1;i<=n;i++)

	{

		scanf("%s",s+1);

		for(j=1;j<=n;j++)

		{

			if(s[j]=='Y')

				Link(i,n+n+n+j,1);

			else

				Link(n+i,n+n+j,1);

		}

	}

	for(i=1;i<=n;i++)

	{

		Link(S,i,0);

		Link(n+n+n+i,T,0);

	}

	cout<<Bisection()<<endl;

}

//0 源点

//1～n 男性第一个点

//n+1~2n 男性第二个点

//2n+1~3n 女性第二个点

//3n+1~4n 女性第一个点

//4n+1 汇点