题目分类：网络流

题意：

有n个男孩n个女孩跳舞，每对男女相互喜欢或者相互不喜欢，每个男孩或女孩最多只愿意和k个不喜欢的异性跳舞，每对只能出现一次，问最多能跳几轮舞。

题解：

考虑判断一个答案是否可行，可以将男孩女孩拆点，分别表示喜欢和不喜欢，每个点中喜欢向不喜欢连k，不喜欢的一对就把两个不喜欢连起来，喜欢的同理，把男孩的喜欢和源连起来，把女孩的喜欢和汇连起来，可以直接枚举答案。

程序：

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int st[3000],ed;
struct node
{
    int next,to,fl,opt;
}g[4000000];
inline void add(int x,int y,int z)
{
//	printf("%d %d %d\n",x,y,z);
	ed++;
	g[ed].to=y;
	g[ed].next=st[x];
	g[ed].fl=z;
	g[ed].opt=ed+1;
	st[x]=ed;
	ed++;
	g[ed].to=x;
	g[ed].next=st[y];
	g[ed].fl=0;
	g[ed].opt=ed-1;
	st[y]=ed;
}
int x1,x2,x3,lev[3000],des;
inline bool makelev()
{
	queue<int>q;
	q.push(0);
	memset(lev,0,sizeof(lev));
	lev[0]=1;
	while (!q.empty())
	{
		x1=q.front();q.pop();
		for (int i=st[x1];i!=0;i=g[i].next)
		{
			if(lev[g[i].to]==0&&g[i].fl!=0)
			{
				q.push(g[i].to);
				lev[g[i].to]=lev[x1]+1;
				if(g[i].to==des)return true;
			}
		}
	}return false;
}	
int stap,sta[3000],spre[3000],stae[3000];
int maxflow;
inline void extend()
{
	int del;
	stap=1;
	sta[1]=0;
	for (int i=0;i<=des;i++)
	{
		spre[i]=st[i];
	}
	while (stap!=0)
	{
		x1=sta[stap];
	//	printf("%d\n",x1);
		if(x1!=des)
		{
            for (;spre[x1]!=0;spre[x1]=g[spre[x1]].next)
            {
                if(g[spre[x1]].fl!=0&&lev[x1]+1==lev[g[spre[x1]].to])
                {
                    break;
                }
            }
            if(spre[x1]!=0)
            {
                stap++;
                stae[stap]=spre[x1];
                sta[stap]=g[spre[x1]].to;
            }
            else
            {
                stap--;lev[x1]=0;
            }
		}
		else
		{
			del=1000000000;
			for (int i=stap;i>=2;i--)
			{
				del=min(del,g[stae[i]].fl);
			}
			maxflow+=del;
			for (int i=stap;i>=2;i--)
			{
				g[stae[i]].fl-=del;
				g[g[stae[i]].opt].fl+=del;
                if(g[stae[i]].fl==0)stap=i-1;
			}
		}
	}
}
inline void dinic()
{
    while (makelev())extend();//,printf("%d\n",maxflow);;
}
int staa;
inline void addone()
{
	for (int i=staa+1;i<=ed;i++)
	{
		if(i%2==1)g[i].fl++;
	}
}
int n,m;
char str[1200];
int a[1200][1200];
int main()
{
	scanf("%d %d",&n,&m);
	des=n+n+n+n+1;
	for (int i=1;i<=n;i++)
	{
		add(i,i+n,m);
		add(i+n+n+n,i+n+n,m);
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		for (int j=1;j<=n;j++)
		{
			if(str[j]=='Y')
			{
				add(i,j+n+n,1);
			}
			else
			{
				add(i+n,j+n+n+n,1);
			}
		}
	}
	staa=ed;
	for (int i=1;i<=n;i++)
	{
		add(0,i,1);
		add(i+n+n,des,1);
	}
	for (int i=1;i<=n+1;i++)
	{
		dinic();
		if(maxflow<i*n){printf("%d\n",i-1);break;}
		addone();
	}
	return 0;
}