（模板）匈牙利算法

匈牙利算法就是不断找增广路的过程

假期的宿舍

题目概述

1. 每个人只能睡自己的床或者自己直接认识人的床
2. 学校自己的学生一部分回家，一部分留校
3. 一部分外校人来找朋友
4. 能否每个人都有床睡觉

输入格式

1. 第一行一个数 表示数据组数。接下来 组数据，每组数据第一行一个数 表示涉及到的总人数。
2. 接下来一行 个数，第 个数表示第 个人是否是在校学生 ( 表示不是， 表示是)。再接下来一行 个数，第 个数表示第 个人是否回家 ( 表示不回家， 表示回家，注意如果第 个人不是在校学生，那么这个位置上的数是一个随机的数，你应该在读入以后忽略它)。
3. 接下来 行每行 个数，第 行第 个数表示 和 是否认识 ( 表示认识， 表示不认识，第 行 个的值为 ，但是显然自己还是可以睡自己的床)，认识的关系是相互的。

思路

1. 可以将人和床看成是两个集合，也就是一个二分图，求二分图的最大匹配问题
2. 学校的学生有自己的床，可以和自己的床匹配。而外校生就能和别人的床匹配。并且数据读入是在校和非在校交叉读入的，如果将左集合设置为所有在学校住的人，右集合设置为所有床，那么编号会乱，要重新编号
3. 可以将左集合设置为所有人，右集合也设置为所有人，做匹配的时候在判断

代码

#include <bits/stdc++.h>
bool vis[55] = {0}, st[55] = {0}, home[55] = {0}; // 是否在增广路中，是否是本校生，是否回家
int lin[55] = {0};
bool peo[55][55];
int n = 0;
bool dfs(int x)
{
    for (int i = 1; i <= n; i++)
    {
        if ( vis[i] == 0 && peo[x][i] && st[i]) // 是本校生才有床
        {
            vis[i] = 1;
            if (lin[i] == 0 || dfs(lin[i]))
            {
                lin[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

void solve()
{
    memset(st, 0, sizeof(st));
    memset(home, 0, sizeof(home));
    memset(lin, 0, sizeof(lin));
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> st[i];
    }
    for (int i = 1; i <= n; i++)
    {
        std::cin >> home[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            std::cin >> peo[i][j];
        }
    }
    // 每个本校生都能睡自己的床
    for (int i = 1; i <= n; i++)
    {
        peo[i][i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if (st[i] == 0 ||(st[i] == 1 && home[i] == 0)) // 如果 不是本校生 或者 本校生不回家 就为他们匹配
        {
            if (dfs(i) == 0)
            {
                std::cout << "T_T" << std::endl;
                return;
            }
        }
    }
    std::cout << "^_^" << std::endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 0;
    std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}