[luoguP1129] [ZJOI2007]矩阵游戏（二分图最大匹配）

传送门

每一行的1和每一列的1不管怎么换还是在同一行和同一列

目标状态中有n个1是不同行且不同列的

那么就是能否找出n个不同行不同列的1

就是每一行选一个不同列的1

如果矩阵中位置i，j为1，那么点i到点j连一条边

跑匈牙利即可

#include <cstdio>

#include <cstring>

#include <iostream>

#define N 201

using namespace std;

int T, n, cnt;

int head[N], to[N * N], nex[N * N], belong[N];

bool vis[N];

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

inline bool dfs(int u)

{

	int i, v;

	for(i = head[u]; ~i; i = nex[i])

	{

		v = to[i];

		if(!vis[v])

		{

			vis[v] = 1;

			if(!belong[v] || dfs(belong[v]))

			{

				belong[v] = u;

				return 1;

			}

		}

	}

	return 0;

}

inline bool solve()

{

	int i, ans = 0;

	for(i = 1; i <= n; i++)

	{

		memset(vis, 0, sizeof(vis));

		ans += dfs(i);

	}

	return ans == n;

}

inline void add(int x, int y)

{

	to[cnt] = y;

	nex[cnt] = head[x];

	head[x] = cnt++;

}

int main()

{

	int i, j, x;

	T = read();

	while(T--)

	{

		cnt = 0;

		memset(head, -1, sizeof(head));

		memset(belong, 0, sizeof(belong));

		n = read();

		for(i = 1; i <= n; i++)

			for(j = 1; j <= n; j++)

			{

				x = read();

				if(x) add(i, j);

			}

		if(solve()) puts("Yes");

		else puts("No");

	}

	return 0;

}