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

Data Range

对于所有数据, 保证:\(n \leq 50, k \leq 30\)

Explanation

一道网络流题, 有一个位置没有想清楚建边建反了所以 WA 了一次

引用 @hzwer 大神的题解一弹:

先把每个人 \(i\) 拆分成 \(i_x\) 和 \(i_y\) 两个节点,\(i_x\) 连向喜欢的人,\(i_y\) 连向不喜欢的人, 容量为 \(1\) (比如如果男生 i 与女生 j 互相喜欢, 则由 \(i_x\) 连向 \(j_x\), 如果 男生 \(i\) 与女生 \(j\) 互相不喜欢, 则由 \(i_y\) 连向 \(j_y\)) , 再将每个男生 \(i_x\) 连向 \(i_y\), 容量为 \(k\); 每个女生 \(i_y\) 连向 \(i_x\), 容量为 \(k\). 由源点向每个男生的 \(x\) 节点连上一条边, 再由每个女生的 \(x\) 节点向汇点连上一条边, 容量均为 \(a\). 最后 从小到大枚举 \(a\), 计算最大流 \(flow\), 若发现 \(a \cdot n \leq flow\) (不满流), 则停止枚举,\(a - 1\) 即为答案.

(或者可以二分)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxN = 60, maxn = 1010, maxm = 500100;
const int infinit = 0x003f3f3f;

bool get_alpha_char(void) { char ch = '\0';
    while (ch != 'Y' && ch != 'N') ch = getchar();
    return ch == 'Y'; }

class Dinic
{
public:
    struct edge
    {
        int u, v, flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt, depth[maxn];
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v, int flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_depth(void)
    {
        memset(depth, 0, sizeof(depth));
        queue<int> que;
        que.push(s);
        depth[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !depth[ep->v]) {
                    depth[ep->v] = depth[p] + 1;
                    que.push(ep->v);
                }
            if (depth[t] > 0)
                return true;
        }
        return false;
    }
    int find(int p, int mn)
    {
        if (p == t)
            return mn;
        int tmp = 0, sum = 0;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (depth[ep->v] == depth[p] + 1 && ep->flow) {
                tmp = find(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            depth[p] = 0; // Eject
        return sum;
    }
    int eval(void)
    {
        int tmp, sum = 0;
        while (make_depth()) {
            tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
    void clear(void)
    {
        memset(edges, 0, sizeof(edges));
        n = s = t = ecnt = 0;
        return ;
    }
} graph;

int n, K;
bool arr[maxN][maxN];

bool judge_flow(int flow_limit)
{
    graph.clear();
    graph.n = 1001;
    graph.s = 0;
    graph.t = 1001;
    // Linking from source to favourable boys
    rep(i, 1, n) graph.add_edge(graph.s, i, flow_limit);
    // Linking from favourable boys to unfavourable boys
    rep(i, 1, n) graph.add_edge(i, 500 + i, K);
    // Linking from favourable girls to target
    rep(i, 1, n) graph.add_edge(500 + n + i, n + i, K);
    // Linking from favourable girls to unfavourable girls
    rep(i, 1, n) graph.add_edge(n + i, graph.t, flow_limit);
    // Linking from boys to girls
    rep(i, 1, n) rep(j, 1, n) {
        if (arr[i][j]) graph.add_edge(i, n + j, 1);
        else graph.add_edge(500 + i, 500 + n + j, 1);
    }
    // Built graph. Run max flow.
    int res = graph.eval();
    // Check delimiations
    if (res < n * flow_limit)
        return false;
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            arr[i][j] = get_alpha_char();
    // Binary searching.
    int l = 0, r = 50;
    int res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (judge_flow(mid)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    // Outputting result
    printf("%d\n", res);
    return 0;
}