1305: [CQOI2009]dance跳舞

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，问题变为在存在限制连边的情况下，男孩与女孩之间是否存在x个完美匹配。
很多网上做法没有写建图正确性证明。。
正确性基于一个霍尔定理的推论：k-正则二分图中有k个不重合的完美匹配，意味着找到一个完美匹配删除它，仍存在k - 1个完美匹配，证明见https://wenku.baidu.com/view/14a976713169a4517623a355.html/show/P3153第12页定理13.13
网上见图方法很多，每一个流代表连一条边，最后形成的是k-正则二分图。
这里就不再写了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a < b ? a : b;}
inline int abs(int x){return x < 0 ? -x : x;}
inline void swap(int &x, int &y){int tmp = x;x = y;y = tmp;}
inline void read(int &x)
{
    x = 0;char ch = getchar(), c = ch;
    while(ch < '0' || ch > '9') c = ch, ch = getchar();
    while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
    if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
const int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
const int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
struct Edge
{
    int u,v,w,nxt;
    Edge(int _u, int _v, int _w, int _nxt){u = _u;v = _v;w = _w;nxt = _nxt;}
    Edge(){}
}edge[1000010];
int head[100010], cnt = 1, S, T, q[100010], he, ta, h[100010], ans;
inline void insert(int a, int b, int c)
{
    edge[++ cnt] = Edge(a, b, c, head[a]), head[a] = cnt;
    edge[++ cnt] = Edge(b, a, 0, head[b]), head[b] = cnt;
}
bool bfs()
{
    memset(h, -1, sizeof(h)), h[S] = 0, he = ta = 0, q[ta ++] = S;
    while(he < ta)
    {
        int now = q[he ++];
        for(int pos = head[now];pos;pos = edge[pos].nxt)
        {
            int v = edge[pos].v;
            if(edge[pos].w && h[v] == -1)
                h[v] = h[now] + 1, q[ta ++] = v;
        }
    }
    return h[T] != -1;
}
int dfs(int x, int f)
{
    if(x == T) return f;
    int used = 0, w;
    for(int pos = head[x];pos;pos = edge[pos].nxt)
    {
        int v = edge[pos].v;
        if(h[v] == h[x] + 1)
        {
            w = dfs(v, min(edge[pos].w, f - used));
            edge[pos].w -= w;
            edge[pos ^ 1].w += w;
            used += w;
            if(used == f) return f;
        }
    }
    if(!used) h[x] = -1;
    return used;
}
void dinic()
{
    while(bfs()) ans += dfs(S, INF);
}
int n, k, num[101][2][2], tot;
char g[101][101];
int main()
{
    read(n), read(k);
    for(int i = 1;i <= n;++ i)
    {
        scanf("%s", g[i] + 1);
        num[i][0][0] = ++ tot, num[i][0][1] = ++ tot;
        num[i][1][0] = ++ tot, num[i][1][1] = ++ tot;
        insert(num[i][0][0], num[i][0][1], k);
        insert(num[i][1][1], num[i][1][0], k);
    }
    for(int i = 1;i <= n;++ i)
        for(int j = 1;j <= n;++ j)
            if(g[i][j] == 'Y')
                insert(num[i][0][0], num[j][1][0], 1);
            else
                insert(num[i][0][1], num[j][1][1], 1);
    int i = 0;S = tot + 1, T = S + 1;
    for(i = 1;;++ i)
    {
        for(int j = 1;j <= n;++ j)
            insert(S, num[j][0][0], 1), insert(num[j][1][0], T, 1);
        dinic();
        if(ans != n * i) break;
    }
    printf("%d", i - 1);
    return 0;
}