记录编号	155718	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2007] 矩阵游戏	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.124 s
提交时间	2015-03-29 22:36:27	内存使用	1.55 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define getc() getchar() 
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 404, maxm = 81004, INF = 0x3f3f3f3f;
struct Edge{int to, cast;Edge *rev;void init(int a, int c, Edge *r){to = a,cast = c, rev = r;}}E[maxm], *Eend;
#include <queue>
Edge *adj[maxn][maxn>>1];
int N, T, adj_size[maxn], dis[maxn], NowE[maxn];
bool vis[maxn];

inline void AddE(int u, int v, int c){
	Eend->init(v, c, Eend+1);adj[u][adj_size[u]++] = Eend++;
	Eend->init(u, 0, Eend-1);adj[v][adj_size[v]++] = Eend++;
}

inline bool get01(){register char c;while((c = getchar()) != '0' && c != '1');return c - '0';}
inline void init(){
	getd(N);T = N + 1;
	int i, j, t;
	Eend = E;
	memset(adj_size, 0, sizeof(adj_size));
	for(i = 1;i <= N;++i)for(j = 1;j <= N;++j)if(get01())
		AddE(i, j + T, 1);
	for(i = 1;i <= N;++i)AddE(0, i, 1), AddE(i + T, T, 1);
}

inline bool BFS(){
	memset(vis, 0, sizeof(vis));
	static queue<int> Q;Q.push(0);vis[0] = true;
	int cur, i;
	Edge *e;
	while(!Q.empty()){
		cur = Q.front();Q.pop();
		for(i = 0;i < adj_size[cur];++i)if((e = adj[cur][i])->cast && !vis[e->to]){
			dis[e->to] = dis[cur] + 1;
			vis[e->to] = true;
			Q.push(e->to);
		}
	}
	return vis[T];
}

int DFS(int cur, int res){
	if(cur == T || !res)return res;
	int i, ans = 0, t;
	Edge *e;
	for(i = NowE[cur];i < adj_size[cur] && res;++i)if(dis[(e = adj[cur][i])->to] == dis[cur] + 1 && e->cast){
		t = DFS(e->to, min(res, e->cast));
		ans += t, res -= t;
		e->cast -= t, e->rev->cast += t;
	}
	return ans;
}

inline void work(){
	int ans = 0;
	while(BFS()){
		memset(NowE, 0, sizeof(NowE));
		ans += DFS(0, INF);
	}
	if(ans == N)printf("Yes\n");
	else printf("No\n");
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(qmatrix);
#endif
	int t;getd(t);
	while(t--){
		init();
		work();
	}

#ifdef DEBUG
	printf("\n%lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}