「BZOJ-1305」dance跳舞最大流

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

链接

bzoj-1305

输入

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

输出

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

样例

输入

1
2
3
4
3 0
YYY
YYY
YYY

输出

1
3

$N<=50, K<=30$

题解

对于每个人,假设其编号为i,则把它拆成ix和iy两个点,ix与喜欢的人的x节点连边,iy与不喜欢的人的y节点连边,容量均为1,然后若此人为男生,则从s向ix连容量为a的边,ix再向iy连容量为k的边,若此人为女生,则从ix向t连容量为a的边,iy再向ix连容量为k的边。从1开始枚举a, 假若未满流,则输出a-1即为答案。或者可以二分a。

代码

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
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <vector>
using namespace std;
const int inf = 2100000000;
inline void R(int &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-') {
p = 1;
}
} while (!isdigit(ch));
while (isdigit(ch)) {
v = (v + (v << 2) << 1) + (ch^'0');
ch = getchar();
}
if (p)
v = -v;
}
int n, k;
bool ma[55][55];
struct node {
int length, pa, to;
node(int to, int length, int pa): to(to), length(length), pa(pa) {
}
node() {
}
};
vector<node>q[300];
int dis[300], gap[300], temp[300];
inline void create(const int &x, const int &y, const int &z) {
q[x].push_back(node(y, z, q[y].size()));
q[y].push_back(node(x, 0, q[x].size() - 1));
}
inline int sap(int x, int flow, const int &s, const int &t) {
if (x == t)
return flow;
int ret = 0;
int f;
//cout<<"x="<<x<<'\n';
for (int i = temp[x]; i < q[x].size(); ++i) {
node *p = &q[x][i];
if (dis[x] == dis[p->to] + 1 && p->length) {
f = sap(p->to, min(flow - ret, p->length), s, t);
p->length -= f;
q[p->to][p->pa].length += f;
temp[x] = i;
if ((ret += f) == flow)return flow;
}
}
temp[x] = 0;
if (!(--gap[dis[x]])) dis[s] = 4 * n + 2;
gap[++dis[x]]++;
return ret;
}
int main() {
// scanf("%d%d",&n,&k);
R(n);
R(k);
int s = 0, t = n * 4 + 1;
//cout<<"t="<<t<<'\n';
char ch[101];
for (int i = 1; i <= n; ++i) {
scanf("%s", ch);
for (int j = 0; j < n; ++j) {
if (ch[j] == 'Y') {
ma[i][j + 1] = 1;
}
}
}
for (int a = 1; a <= n; ++a)
{
int ans = 0;
memset(dis, 0, sizeof(dis));
memset(q, 0, sizeof(q));
memset(gap, 0, sizeof(gap));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (ma[i][j])
{
create(i, j + n, 1);
// cout<<"i="<<i<<" j="<<j<<'\n';
}
else
create(i + n * 2, j + n * 3, 1);
}
}
for (int i = 1; i <= n; ++i) {
create(i, i + n * 2, k);
create(i + n * 3, i + n, k);
}
for (int i = 1; i <= n; ++i) {
create(s, i, a);
create(i + n, t, a);
}
gap[0] = 4 * n + 2;
// cout<<"a="<<a<<'\n';
while (dis[s] < 4 * n + 2) ans += sap(s, inf, s, t);
// cout<<"ans="<<ans<<'\n';
if (ans < a * n) {
cout << a - 1;
return 0;
}
}
cout << n;
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 输入
  3. 3. 输出
  4. 4. 样例
    1. 4.1. 输入
    2. 4.2. 输出
  5. 5. 题解
  6. 6. 代码