#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4 + 5, M = 1e6 + 5, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], d[N], cur[N];
int n, m, k, cnt, S, T, res, idx, x, y, c, a, b;
char ch;
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], w[idx] = 0, h[b] = idx++;
}
bool bfs()
{
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(S), d[S] = 0, cur[S] = h[S];
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1 && w[i])
            {
                d[j] = d[t] + 1, cur[j] = h[j];
                if (j == T)
                    return true;
                q.push(j);
            }
        }
    }
    return false;
}
int find(int u, int limit)
{
    if (u == T)
        return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        int j = e[i];
        cur[u] = i;
        if (d[j] == d[u] + 1 && w[i])
        {
            int t = find(j, min(limit - flow, w[i]));
            if (!t)
                d[j] = -1;
            w[i] -= t, w[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}
int Dinic()
{
    int r = 0, flow;
    while (bfs())
        while (flow = find(S, INF))
            r += flow;
    return r;
}
int main()
{
    cin >> n >> k, memset(h, -1, sizeof(h));
    S = 0, cnt = 2 * n, T = ++cnt;
    for (int i = 1; i <= n; i++)
    {
        add(S, i, 1), add(i + n, T, 1), add(i, ++cnt, k);
        for (int j = 1; j <= n; j++)
        {
            cin >> ch;
            if (ch == 'Y')
                add(i, j + n, 1);
            else
                add(cnt, j + n, 1);
        }
    }
    for (int flow = 1;; flow++)
    {
        res = Dinic();
        if (res < n)
            cout << flow - 1 << endl, exit(0);
        for (int i = 0; i < idx; i += 2)
        {
            a = e[i ^ 1], b = e[i];
            if (a == S || b == T)
                w[i] = 1, w[i ^ 1] = 0;
        }
    }
}

不是很懂为什么WA两个，思路是建立新点专门负责跟不喜欢的女生配对，分配k流量。

保留非S，T关联边（每次只重新分男女生次数，保留历史配对）的流量，然后反复求增广路