[ZJOI2007] 矩阵游戏 - 二分图匹配

题意：问一个\(0-1\)方阵是不是非奇异的

其实我真的很想求行列式

#include <bits/stdc++.h>
using namespace std;
#define N 505
int n,m,p,cx[N],cy[N],vis[N];
std::vector<int> e[N];
int dfs(int u,int Time) {
    for(int i=0;i<(int)e[u].size();++i) {
        int v=e[u][i];
        if(vis[v]^Time) {
            vis[v]=Time;
            if(!cy[v]||dfs(cy[v],Time)) {
                cx[u]=v; cy[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
void solve() {
    n=m=p=0;
    memset(cx,0,sizeof cx);
    memset(cy,0,sizeof cy);
    memset(vis,0,sizeof vis);
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++) e[i].clear();
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            int t;
            cin>>t;
            if(t) e[i].push_back(j);
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i) ans+=dfs(i,i);
    if(ans==n) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
int main() {
    int t;
    cin>>t;
    while(t--) solve();
}

[ZJOI2007] 矩阵游戏 - 二分图匹配

原文：https://www.cnblogs.com/mollnn/p/12262519.html