记录编号	270817	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2009] 假期的宿舍	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2016-06-15 11:42:41	内存使用	0.32 MiB

#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a = 0, minus = 1;
	char ch = getchar();
	if(ch == '-')       minus = -1;
	while(ch < '0' || ch > '9'){
		ch = getchar();
		if(ch == '-')	minus = -1;
	}
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
	return a * minus;
}

bool student[60], gohome[60], beside[60][60], visited[60]; 
int n;
int b[60];//b[i] == j表示集合a中i匹配集合b中j 

int Hungary(int x)
{
	for(int i = 1; i <= n; i++){
		if(beside[x][i] && !visited[i]){
			visited[i] = 1;
			if(b[i] == -1 || Hungary(b[i])){
				b[i] = x;
				return 1;
			}
		}	
	}
	return 0;
}

void Work()
{
	for(int i = 1; i <= n; i++){
		if(!student[i] || (student[i] && !gohome[i])){//需要睡在学校
			memset(visited, 0, sizeof(visited));
			if(!Hungary(i)){
				puts("T_T");
				return ;
			}
		}
	}
	puts("^_^");
}

void Init()
{
	memset(b, -1, sizeof(b));
	n = Read();
	for(int i = 1; i <= n; i++)
		student[i] = Read();
	for(int i = 1; i <= n; i++)
	{
		int tmp = Read();
		if(student[i] && tmp == 1)	gohome[i] = 1;
		else gohome[i] = 0;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			beside[i][j] = Read();
			if(i == j)	beside[i][j] = 1;
			if(!student[j])	beside[i][j] = 0;
		}
	}
//	for(int i = 1; i <= n; i++){
//		for(int j = 1; j <= n; j++)
//			printf("%d ",beside[i][j]);
//		puts("");	
//	}
	Work();
}

int main()
{
	freopen("zjoi09holiday.in", "r", stdin);
	freopen("zjoi09holiday.out", "w", stdout);
	int T = Read();
	while(T--)	Init();	
	fclose(stdin);
	fclose(stdout);
	return 0;
}/*
1 3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

*/