「Bzoj 1433」「ZJOI2009」假期的宿舍 (二分图最大匹配)

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

#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;
}