「BZOJ1305」[CQOI2009]dance跳舞

Description

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

Input

第一行包含两个整数nnkk。以下nn行每行包含nn个字符,其中第i行第jj个字符为Y当且仅当男孩ii和女孩jj相互喜欢。

Output

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

Sample Input

1
2
3
4
3 0
YYY
YYY
YYY

Sample Output

1
3

HINT

N50,K30N\leq 50,K\leq 30

Solution

如果已经知道了舞曲数目是aa
首先男生分裂两个点XiX_iXi+nX_{i+n},分别表示和喜欢的人跳舞和不喜欢的人跳舞
女生同样的,分裂为YiY_iYi+nY_{i+n}
连边(S,Xi,a)(S,X_i,a)(Xi,Xi+n,k)(X_i,X_{i+n},k)(Yi,Yi+n,k)(Y_i,Y_{i+n},k)(Yi+n,T,a)(Y_{i+n},T,a)
对于每一对相互喜欢的连边(Xi,Yj+n,1)(X_i,Y_{j+n},1)
对于每一对不相互喜欢的连边(Xi+n,Yj,1)(X_{i+n},Y_j,1)
然后跑dinic看看最大流是否为a×na\times n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 60, M = 60*60*8;
int n, m;
bool g[N][N];
char s[N];
int res;
int S, T;
struct Edge {
int u, v, nxt, f;
}e[M];
int en, head[N*6];
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
const int inf = 1e9;
int d[N*6];
bool bfs() {
queue<int>q;
q.push(S);
memset(d, 0, sizeof d);
d[S] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f) {
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == T) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == T) return flow;
int rest = flow, k;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(flow, e[i].f));
e[i ^ 1].f += k;
e[i].f -= k;
rest -= k;
}
return flow - rest;
}
void solve(int val) {
S = 4 * n + 1;
T = 4 * n + 2;
en = 1;
for(int i = 1; i <= T; ++i) head[i] = 0;
for(int i = 1; i <= n; ++i) {
addedge(S, i, val);
addedge(i, i + n, m);
addedge(i + 2 * n, i + 3 * n, m);
addedge(i + 3 * n, T, val);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(g[i][j])
addedge(i, j + n * 3, 1);
else
addedge(i + n, j + n * 2, 1);
int y;
while(bfs()) {
while(y = dinic(S, inf)) res += y;
}
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
scanf("%s", s+ 1);for(int j = 1; j <= n; ++j)
g[i][j] = (s[j] == 'Y');
}
int l = 0, r = n + 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
res = 0;
solve(mid);
if(res == mid * n) l = mid;
else r = mid;
}
writeln(l);
return 0;
}