Bzoj 1433(二分图最大匹配)

BZOJ 1433
题意:见上。
本题很容易看出是一个二分图最大匹配的题目。
将左边点抽象化为人,右边为床,边就是分配。然后分类讨论一下连边情况,最后看二分图最大匹配是否等于要安排的人即可。
知识点:
1、初始化数组要全部初始化,输入数组也要初始化
2、赋值时考虑是否会覆盖之前的值

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
const int MAXN = 55;
int n, a[MAXN], b[MAXN], ma[MAXN][MAXN], lk[MAXN], vis[MAXN], cnt;
bool hungary(int u) {
for (int v = 1; v <= n; v++) if (ma[u][v]) {
if (vis[v] != cnt) {
vis[v] = cnt;
if (!lk[v] || hungary(lk[v])) {
lk[v] = u;
return true;
}
}
}
return false;
}
void clean() {
ms(ma, 0), ms(lk, 0), ms(vis, 0);
}
int solve() {
clean();
int ans = 0, tot = 0;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), tot += (!a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]), tot += (a[i] == 1 && b[i] == 0);
for (int i = 1; i <= n; i++)
for (int x, j = 1; j <= n; j++) {
scanf("%d", &x);
if (i == j && a[i] == 1 && b[i] == 0) {ma[i][j] = 1; continue;}
if (a[j] == 1) ma[i][j] = x;
}
for (int i = 1; i <= n; i++) if ((!a[i]) || (a[i] == 1 && b[i] == 0)) ans += hungary(cnt = i);
if (ans == tot) printf("^_^\n"); else printf("T_T\n");
return 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) scanf("%d", &n), solve();
return 0;
}
------ 本文结束 ------