C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 632K, 提交时间: 2020-03-27 18:17:06

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int ans;
int cnt;
int head[1010],q[1010],dis[1010];
int n,k,T;
struct edge
{
	int to,nxt;
	int flow;
}e[500050];
inline void addedge(int x,int y,int fl)
{
	e[++cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
	e[cnt].flow=fl;
	e[++cnt].to=x;
	e[cnt].nxt=head[y];
	head[y]=cnt;
	e[cnt].flow=0;
}
bool mp[1010][1010];
inline bool bfs()
{
	int ql=0,qr=1;
	q[1]=0;
	memset(dis,0,sizeof(dis));
	dis[0]=1;
	while(ql<qr)
	{
		int x=q[++ql];
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(e[i].flow&&!dis[y])
			{
				dis[y]=dis[x]+1;
				q[++qr]=y;
			}
		}
	}
	if(dis[T]) return true;
	return false;
}
inline int dfs(int x,int flow)
{
	if(x==T) return flow;
	int d,used=0;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(e[i].flow&&dis[y]==dis[x]+1)
		{
			d=dfs(y,min(flow,e[i].flow));
			e[i].flow-=d;
			e[i^1].flow+=d;
			used+=d;
			if(used==flow)
			return flow;
		}
	}
	if(!used)
	dis[x]=-1;
	return used;
 } 
inline void dinic()
{
	while(bfs())
	ans+=dfs(0,inf);
}
inline void build(int x)
{
	cnt=1;
	memset(head,0,sizeof(head));
	for(int i=1;i<=n;i++)
    {
    	addedge(0,i,x);
    	addedge(i,i+500,k);
    	addedge(i+n+500,i+n,k);
    	addedge(i+n,T,x);
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(mp[i][j]) addedge(i,n+j,1);
	else addedge(i+500,n+j+500,1);
}
int main()
{
	scanf("%d%d",&n,&k);
	T=1001;
	for(int i=1;i<=n;i++)
	{
		char ch[51];
		scanf("%s",ch);
		for(int j=1;j<=n;j++)
		if(ch[j-1]=='Y')
		mp[i][j]=1;
	}
	int mx=0,l=0,r=50;
	while(l<=r)
	{
		int mid=l+r>>1;
		build(mid);
		ans=0;
		dinic();
		if(ans>=n*mid)
		mx=mid,l=mid+1;
		else
		r=mid-1;
	}
	cout<<mx;
}