1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

ˆ ˆ

对于30% 的数据满足1 ≤ n ≤ 12。
对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。

题目分析：

这题一看就是二分图最大匹配 但是建图非常恶心
分三种情况：
1：在校学生并且不回家 向自己所有认识的在校学生的床连一条边 包括自己
2：不在校学生 向所有自己认识的在校学生的床连一条边
3：在校学生，并且回家 连一条自己家里的床(i->n+i)
最后数组开够 时刻注意不在校学生没有自己的床

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int head[1200],to[300010],net[300010],hom[1100],sch[1100];
int n,t,tot;
bool vis[1200];
int line[1200];
int map[100][1000];
void init()
{
	tot=0;
	n=0;
	memset(head,0,sizeof head);
	memset(to,0,sizeof to);
	memset(map,0,sizeof map);
	memset(net,0,sizeof net);
	memset(hom,0,sizeof hom);
	memset(sch,0,sizeof sch);
	memset(line,0,sizeof line);
	memset(vis,0,sizeof vis);
}
void add(int x,int y)
{
	net[++tot]=head[x];
	to[tot]=y;
	head[x]=tot;
}
int dfs(int x)
{
	for(int i=head[x];i;i=net[i])
		if(!vis[to[i]])
		{
			vis[to[i]]=1;
			if(line[to[i]]==0||dfs(line[to[i]]))
			{
				line[to[i]]=x;
				return 1;
			}
		}
	return 0;
}
int check()
{
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof vis);
		if(!dfs(i)) return 0;
	}
	return 1;
}
char a=84;
int main()
{
	scanf("%d",&t);
	while(t)
	{
		t--;
		init();
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&sch[i]);
		for(int i=1;i<=n;i++) scanf("%d",&hom[i]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&map[i][j]);
		for(int i=1;i<=n;i++)
		{
			if(sch[i]==1)
			{
				if(hom[i]==1) add(i,n+i);
				else for(int j=1;j<=n;j++)
					if((i==j)||(sch[j]&&map[i][j])) add(i,j);
			}
			else 
			{
				for(int j=1;j<=n;j++)
					if(sch[j]&&map[i][j]) add(i,j);
			}
		}	
		if(!check()) printf("%c%c%c\n",a,a+11,a);
		else printf("%c%c%c\n",a+10,a+11,a+10);
	}
    return 0;
}