记录编号	272216	评测结果	AAAAAAAAAA
题目名称	1386.文理分班	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-06-16 17:49:00	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100
using namespace std;
int edge[maxn][maxn],q,n,cx[maxn],cy[maxn],cnt1,cnt2,ans,a[maxn],b[maxn];
bool stay[maxn],flag[maxn],vis[maxn];
void _work();
int _path(int);
void clean();
int Main();
int haha=Main();
int main(){;}
int Main(){
	freopen("divideb.in","r",stdin);
	freopen("divideb.out","w",stdout);
	scanf("%d",&q);
	while(q--){
		clean();
		int n;scanf("%d",&n);
		int x;
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			if(x==1){
				flag[i]=1;
				cnt2++;
				b[cnt2]=i;
			
			}
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			if((flag[i]&&x==0)||!flag[i]){
				stay[i]=1;
				cnt1++;
				a[cnt1]=i;
			}
		}
		for(int i=1;i<=n;i++)edge[i][i] = 1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&x);
				if(x==1&&(stay[i]||!flag[i])&&flag[j]){
					edge[i][j]=1;
				}
			}
		}
		_work();
		if(ans==cnt1){
			printf("^_^\n");
		}
		else{
			printf("T_T\n");
		}
	}
}
void clean(){
	memset(edge,0,sizeof(edge));
	memset(flag,0,sizeof(flag));
	memset(stay,0,sizeof(stay));
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(cx,0,sizeof(cx));
	memset(cy,0,sizeof(cy));
	cnt2=0;cnt1=0;ans=0;
}
void _work(){
	for(int i=1;i<=cnt1;i++){
		if(!cx[a[i]]){
			memset(vis,0,sizeof(vis));
			ans+=_path(a[i]);
		}
	}
}
int _path(int u){
	int v;
	for(v=1;v<=cnt2;v++){
		if(edge[u][b[v]]&&!vis[b[v]]){
			vis[b[v]]=1;
			if(!cy[b[v]]||_path(cy[b[v]])){
				cx[u]=b[v];cy[b[v]]=u;
				return 1;
			}
		}
	}
	return 0;
}