记录编号	610257	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2009] 假期的宿舍	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.145 s
提交时间	2025-12-18 22:58:15	内存使用	3.69 MiB

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 55;
int n;
int T;
bool at[MAXN];
int home[MAXN];
vector<int> g[MAXN];
int mac[MAXN];
bool vis[MAXN];

bool dfs(int u){
	for(int &v : g[u]){
		if(!vis[v]){
			vis[v] = 1;
			if(mac[v] == -1 || dfs(mac[v])){
				mac[v] = u;
				return true;
			}
		}
	}
	return false;
}

int hungary(int n){
	int cnt = 0;
	memset(mac, -1, sizeof(mac));
	for(int i = 1;i <= n;i ++){
		memset(vis, 0, sizeof(vis));
		if(!at[i] || (at[i] && !home[i])) cnt += dfs(i);
	}
	return cnt;
}

int main(){

	cin >> T;

	while(T --){
		int sum = 0;
		cin >> n;
		for(int i = 1;i <= n;i ++) g[i].clear();
		for(int i = 1;i <= n;i ++){
			cin >> at[i];
		}
		for(int i = 1;i <= n;i ++){
			cin >> home[i];
			if(!home[i] && at[i]){
				g[i].push_back(i);
			}
        }
        for(int i = 1;i <= n;i ++){
            if(!at[i] || (at[i] && !home[i])) sum ++;
        }
		for(int i = 1;i <= n;i ++){
			for(int j = 1;j <= n;j ++){
				bool rela; cin >> rela;
				if(rela && at[j]){
					g[i].push_back(j);
				}
			}
		}
		if(hungary(n) == sum){
			cout << "^_^\n";
		}
		else{
			cout << "T_T\n";
		}
	}


	return 0;
}