Description

一次舞会有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

 

把男孩女孩都拆点为x,y

S向x连边，容量为a，y向汇点连边，容量为a

a可以二分，可以枚举（反正只有30）

男生x-->y连边为k，女生y-->x连边为k，男生喜欢女生在左部连边，反之在右部

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int inf=100000000,N=1005; 7 struct ee{
    int to,next,f;}e[500001]; 8 int head[N],q[N*2],dis[N],map[N][N]; 9 int S,T,n,m,cnt=1,ans,w,k,mx;10    11 void ins(int u,int v,int f){12     e[++cnt].to=v;e[cnt].f=f;e[cnt].next=head[u];head[u]=cnt;13     e[++cnt].to=u;e[cnt].f=0;e[cnt].next=head[v];head[v]=cnt;14 }15    16 bool bfs(){17     for (int i=1;i<=T;i++) dis[i]=inf;18     int h=0,t=1,now;19     q[1]=S;dis[S]=0;20     while(h!=t){21         now=q[++h];22         for (int i=head[now];i;i=e[i].next){23             int v=e[i].to;24             if (e[i].f&&dis[now]+1
          
           >1;75         build(mid);76         ans=0;while(bfs()) ans+=dinic(S,inf);77         if(ans>=n*mid){mx=mid;l=mid+1;}78         else r=mid-1;79     }80     printf("%d",mx);81 }