Description

Input

Output

Sample Input

Sample Output

HINT

Source

【题解】

把人和床建二分图直接网络流即可。

# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <queue>

using namespace std;

const int M=600010;
int next[M],to[M],S,T,c[M],head[M],tot=1,flow[M];
queue<int> q;

inline void add(int u,int v,int fl) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	flow[tot]=fl;
}

inline void Add(int u,int v,int fl) {
	add(u,v,fl);
	add(v,u,0);
}

inline bool bfs() {
	while(!q.empty()) q.pop();
	memset(c,-1,sizeof(c));
	c[S]=1;q.push(S);
	while(!q.empty()) {
		int top=q.front();q.pop();
		for (int i=head[top];i;i=next[i]) {
			int _to=to[i];
			if(c[_to]>=0 || flow[i]==0) continue;
			c[_to]=c[top]+1;
			q.push(_to);
			if(_to==T) return 1;
		}
	}
	return 0;
}

inline int dfs(int x,int low) {
	if(x==T) return low;
	int r=low,fl;
	for (int i=head[x];i;i=next[i]) {
		int _to=to[i];
		if(c[_to]!=c[x]+1 || flow[i]==0) continue;
		fl=dfs(_to,min(r,flow[i]));
		r-=fl;
		flow[i]-=fl;
		flow[i^1]+=fl;
		if(!r) return low;
	}
	if(r==low) c[x]=-1;
	return low-r;
}

inline int dinic() {
	int ans=0;
	while(bfs()) ans+=dfs(S,200011300);
	return ans;
}

int Ly,n,ss[M];

int main() {
	scanf("%d",&Ly);
	
	while(Ly--) {
		tot=1;S=0,T=110;
		int all=0;
		memset(head,0,sizeof(head));
		scanf("%d",&n);
		for (int i=1;i<=n;++i) {
			scanf("%d",&ss[i]);
			if(ss[i]==1) Add(i+n,T,1);
		}
		for (int i=1,x;i<=n;++i) {
			scanf("%d",&x);
			if((ss[i] && x==0) || ss[i]==0) {
				Add(S,i,1);
				++all;
			}
		}
		for (int i=1,x;i<=n;++i)
			for (int j=1;j<=n;++j) {
				scanf("%d",&x);
				if(x || i==j) Add(i,j+n,1);
			}
		int s2=dinic();
		if(s2==all) puts("^_^");
		else puts("T_T");	
	}
	return 0;
}