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

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

仅一个数，即舞曲数目的最大值。

题解:

二分的答案为 $a$.

把每个人拆成两个点，从“喜欢”到“不喜欢”连一条容量为 $k$ 的边.

从 $S$ 向“男孩喜欢”连一条容量为 $a$ 的边，从“女孩喜欢”往 $T$ 连一条容量为 $a$ 的边.

然后对于每对男孩女孩:

1. 不喜欢： 从“男孩不喜欢”到“女孩不喜欢”连一条容量为 $1$ 的边.

2. 喜欢：从“男孩喜欢”到“女孩喜欢”连一条容量为 $1$ 的边.

// luogu-judger-enable-o2

#include <bits/stdc++.h>

#define maxn 400

#define inf 10000000

#define setIO(s) freopen(s".in","r",stdin)

#define r1(i) i

#define r2(i) (i+n)

#define r3(i) (i+n+n)

#define r4(i) (i+n+n+n)

using namespace std;

char str[100];

int G[maxn][maxn];

namespace Dinic{

    struct Edge{

        int from,to,cap;

        Edge(int u=0,int v=0,int c=0):from(u),to(v),cap(c){}

    };

    vector<int>G[maxn];

    vector<Edge>edges;

    queue<int>Q;

    int vis[maxn],d[maxn],curr[maxn];

    int s,t;

    void addedge(int u,int v,int c){

        edges.push_back(Edge(u,v,c)),edges.push_back(Edge(v,u,0));

        int m=edges.size();

        G[u].push_back(m-2),G[v].push_back(m-1);

    }

    int BFS(){

        memset(vis,0,sizeof(vis));

        d[s]=0,vis[s]=1, Q.push(s);

        while(!Q.empty()){

            int u=Q.front();Q.pop();

            for(int sz=G[u].size(),i=0;i<sz;++i){

                Edge r=edges[G[u][i]];

                if(!vis[r.to]&&r.cap>0) {

                    vis[r.to]=1,d[r.to]=d[u]+1;

                    Q.push(r.to);

                }

            }

        }

        return vis[t];

    }

    int dfs(int x,int cur){

        if(x==t) return cur;

        int f,flow=0;

        for(int sz=G[x].size(),i=curr[x];i<sz;++i){

            curr[x]=i;

            Edge r=edges[G[x][i]];

            if(d[r.to]==d[x]+1&&r.cap>0){

                f=dfs(r.to,min(cur,r.cap));

                cur-=f,flow+=f,edges[G[x][i]].cap-=f,edges[G[x][i]^1].cap+=f;

            }

            if(cur<=0) break;

        }

        return flow;

    }

    int maxflow(){

        int flow=0;

        while(BFS()) memset(curr,0,sizeof(curr)),flow+=dfs(s,inf);

        return flow;

    }

    void re(){

        for(int i=0;i<maxn;++i) G[i].clear();

        edges.clear();

    }

};

int n,k;

bool check(int t){

    Dinic::re();

    Dinic::s=0,Dinic::t=396;

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

        Dinic::addedge(r1(i),r2(i),k);

        Dinic::addedge(r3(i),r4(i),k);

        Dinic::addedge(Dinic::s,r1(i),t);

        Dinic::addedge(r4(i),Dinic::t,t);

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

            if(G[i][j])

                Dinic::addedge(r1(i),r4(j),1);

            else

                Dinic::addedge(r2(i),r3(j),1);

        }

    }

    return Dinic::maxflow()==t*n;

}

int main(){

    // setIO("input");

    scanf("%d%d",&n,&k);

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

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

        for(int j=1;j<=n;++j) if(str[j]=='Y') G[i][j]=1;

    }

    int l=1,r=n,mid,ans=0;

    while(l<=r){

        mid=(l+r)>>1;

        if(check(mid)) ans=mid,l=mid+1;

        else r=mid-1;

    }

    printf("%d",ans);

    return 0;

}