「Bzoj 1059」「ZJOI2007」矩阵游戏 (二分图最大匹配)

Bzoj 1059
想算法的时候自己多搞几个数据找一找规律和结论，特别是这种看起来就会有规律和结论的题目，很重要！
通过搞几个数据，发现：在同行同列的两个$1$，它们对答案的贡献是相同的，因为无论怎么调换，这两个$1$都会在同行同列。又因为要对角线上都是$1$，所以问题转化为：找到$n$个点使得这$n$个点不在同行同列上。这样我们把$x$坐标弄到左边，$y$坐标弄到右边，如果$(i,j)=1$，在左边$i$连一条边到右边$j$，然后做一个二分图最大匹配，如果不能全部都匹配，就不能完成了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 200 + 5; 
vector<int> G[MAXN];
int cnt, n, lk[MAXN], vis[MAXN];
bool hungary(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (vis[v] != cnt) {
            vis[v] = cnt;
            if (!lk[v] || hungary(lk[v])) {
                lk[v] = u;
                return true;
            }
        }
    }
    return false;
}
void clean() {
    for (int i = 0; i <= n; i++) lk[i] = vis[i] = 0, G[i].clear();
}
void solve() {
    scanf("%d", &n);
    clean();
    for (int i = 1; i <= n; i++) {
        for (int x, j = 1; j <= n; j++) {
            scanf("%d", &x);
            if (x == 1) G[i].push_back(j);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!hungary(cnt = i)) {
            printf("No\n");
            return ;
        }
    }
    printf("Yes\n");
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}