题意：给出一个矩阵，只有0和1，问是否可以通过行交换和列交换使得方阵的主对角线(左上角到右下角的连线)上的格子均为1
思路：我们可以把矩阵中1的位置xy看作一条从x连到y的边，所以就可以建一个二分图，求二分图的最大匹配便是交换行列后的匹配数，若最大匹配数小于n，则no，等于n，则yes
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 210; int n, t, mp[N][N], a, march[N], vis[N]; int F(int x) { for(int i = 1; i <= n; i++) { if(mp[x][i] && !vis[i]) { vis[i] = 1; if(!march[i] || F(march[i])) { march[i] = x; return 1; } } } return 0; } int main() { cin >> t; while(t--) { cin >> n; memset(mp, 0, sizeof mp); memset(march, 0, sizeof march); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { cin >> a; if(a) mp[i][j] = 1; } int ans = 0; for(int i = 1; i <= n; i++) { memset(vis, 0, sizeof vis); ans += F(i); } cout << (ans == n ? "Yes" : "No") << endl; } return 0; }
