记录编号	133621	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2009] 假期的宿舍	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2014-10-28 14:08:28	内存使用	0.30 MiB

/*
	author :hzoi_ztx
	title  :cogs 1356. Dormitory
	ALG    :二分图匹配
	CMT    :

	[2014 10 27]
*/

#include <cstdio>
#include <cstring>

#define  maxn  51

int T ;
int n ;
int pre[maxn] ;
int flag[maxn] ;
int flag2[maxn] ;
int g[maxn][maxn] ;
bool visit[maxn] ;

inline bool find(int u) {
	for (int v = 1 ; v <= n ; v ++ ) {
		if (!g[u][v] || visit[v]) continue ;
		visit[v] = true ;
		if (!pre[v] || find(pre[v])) {
			pre[v] = u ; return true ;
		}
	}
	return false ;
}

inline void KM() {
	int i ;
	for (i = 1 ; i <= n ; i ++ ) {
		if (flag[i]==0 || (flag[i]==1&&flag2[i]==0)) {
			memset(visit , 0 , sizeof(visit)) ;
			if (!find(i)) {
				puts("T_T") ;
				return ;
			}
		}
 	}
	puts("^_^") ;
}

int main() {
	#define READ
	#ifdef  READ
	    freopen("zjoi09holiday.in" ,"r",stdin ) ;
	    freopen("zjoi09holiday.out","w",stdout) ;
	#endif
	int i , j ;
	scanf("%d", &T ) ;
	while ( T -- ) {
		scanf("%d", &n ) ;
		for (i = 1 ; i <= n ; i ++ ) {
			scanf("%d", &flag[i] ) ;
			if (flag[i]>>1) flag[i] = 0 ;
			pre[i] = 0 ;
			/*是否是宠物*/
		}
		for (i = 1 ; i <= n ; i ++ ) {
			scanf("%d", &flag2[i] ) ;
			if (flag2[i]>>1) flag2[i] = 0 ;
			/*是否出去玩*/
		}
		for (i = 1 ; i <= n ; i ++ ) {
			for (j = 1 ; j <= n ; j ++ ) {
				scanf("%d", &g[i][j] ) ;
				if (g[i][j]>>1) g[i][j] = 0 ;
				if (i == j) g[i][j] = 1 ;
				if (!flag[j]) g[i][j] = 0 ;
			}
		}/*建图*/
		KM() ;
	}
	#ifdef  READ
	    fclose(stdin ) ;
	    fclose(stdout) ;
	#else
	    getchar() ; getchar() ;
	#endif
	return 0 ;
}