BZOJ原题链接

洛谷原题链接

对于每个需要床位的人向他能睡的床连边，然后就是二分图最大匹配模板了。

这里用匈牙利算法。

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 55;

const int M = 1e4 + 10;

int fi[M], di[M], ne[M], mtc[M], l;

bool v[M], h[N], sc[N];

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline void add(int x, int y)

{

	di[++l] = y;

	ne[l] = fi[x];

	fi[x] = l;

}

bool dfs(int x)

{

	int i, y;

	for (i = fi[x]; i; i = ne[i])

		if (!v[y = di[i]])

		{

			v[y] = 1;

			if (!mtc[y] || dfs(mtc[y]))

			{

				mtc[y] = x;

				return true;

			}

		}

	return false;

}

int main()

{

	int i, j, n, t;

	t = re();

	while (t--)

	{

		n = re();

		l = 0;

		memset(fi, 0, sizeof(fi));

		memset(mtc, 0, sizeof(mtc));

		for (i = 1; i <= n; i++)

			sc[i] = re();

		for (i = 1; i <= n; i++)

			sc[i] ? h[i] = re() : h[i] = re() ? 0 : 0;

		int k = 0;

		for (i = 1; i <= n; i++)

			if (!sc[i] || (sc[i] && !h[i]))

				k++;

		for (i = 1; i <= n; i++)

		{

			if (!h[i] && sc[i])

				add(i, i + n);

			for (j = 1; j <= n; j++)

				if (re() && !h[i] && sc[j])

					add(i, j + n);

		}

		int s = 0;

		for (i = 1; i <= n; i++)

		{

			memset(v, 0, sizeof(v));

			if (dfs(i))

				s++;

		}

		s ^ k ? printf("T_T\n") : printf("^_^\n");

	}

	return 0;

}