*题目描述：
小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N
*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择
矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换
对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑
色。对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程
序来判断这些关卡是否有解。
*输入：
第一行包含一个整数T，表示数据的组数。接下来包含T组数据，每组数据第一行为一个整数N，表示方阵的大
小；接下来N行为一个N*N的01矩阵（0表示白色，1表示黑色）。
*输出：
输出文件应包含T行。对于每一组数据，如果该关卡有解，输出一行Yes；否则输出一行No。
*样例输入：
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0
*样例输出：
No
Yes
*提示：
【数据规模】
对于100%的数据，N ≤ 200
*题解：
二分图最大匹配。
最终的状态为第i行第i列为黑色，那么把行和列拆成两排点，如果(i,j)这个点时黑色的，那么就从i行向j列连一条边，由于一行只能对应一个列所以时匹配，只有最大匹配是n时输出Yes，不然就是No.
*代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout)
#endif#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
#define cabs(_x) ((_x) < 0 ? (- (_x)) : (_x))
char B[1 << 15], *S = B, *T = B;
inline int F()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
#define maxn 1010
#define maxm 100010
struct Edge
{
Edge *next, *rev;
int to, cap;
}*last[maxn], e[maxm], *ecnt = e, *cur[maxn];
inline void link(R int a, R int b, R int w)
{
*++ecnt = (Edge) {last[a], ecnt + 1, b, w}; last[a] = ecnt;
*++ecnt = (Edge) {last[b], ecnt - 1, a, 0}; last[b] = ecnt;
}
int s, t, ans, dep[maxn];
inline void init()
{
memset(last, 0, sizeof last); ecnt = e; ans = 0;
}
std::queue<int> q;
inline bool bfs()
{
memset(dep, -1, sizeof (dep));
q.push(t); dep[t] = 0;
while (!q.empty())
{
R int now = q.front(); q.pop();
for (R Edge *iter = last[now]; iter; iter = iter -> next)
{
R int pre = iter -> to;
if (iter -> rev -> cap && dep[pre] == -1)
{
dep[pre] = dep[now] + 1;
q.push(pre);
}
}
}
return dep[s] != -1;
}
int dfs(R int x, R int f)
{
if (x == t) return f;
R int used = 0;
for (R Edge* &iter = cur[x]; iter; iter = iter -> next)
{
R int pre = iter -> to;
if (iter -> cap && dep[x] == dep[pre] + 1)
{
R int v = dfs(pre, dmin(iter -> cap, f - used));
iter -> cap -= v;
iter -> rev -> cap += v;
used += v;
if (used == f) return f;
}
}
if (!used) dep[x] = -1;
return used;
}
inline void dinic()
{
while (bfs())
{
memcpy(cur, last, sizeof last);
ans += dfs(s, 0x7fffffff);
}
}
int main()
{
// setfile();
for (R int tim = F(); tim; --tim)
{
init();
R int n = F();
s = 0; t = n << 1 | 1;
for (R int i = 1; i <= n; link(s, i, 1), link(i + n, t, 1), ++i)
for (R int j = 1; j <= n; ++j)
{
R int a = F();
if (a) link(i, j + n, 1);
}
dinic();
if (ans == n) puts("Yes");
else puts("No");
}
return 0;
}
