NC20472. [ZJOI2007]矩阵游戏
描述
输入描述
第一行包含一个整数T，表示数据的组数。
接下来包含T组数据，每组数据第一行为一个整数N，表示方阵的大小；
接下来N行为一个N*N的01矩阵（0表示白色，1表示黑色）。
输出描述
输出文件应包含T行。
对于每一组数据，如果该关卡有解，输出一行Yes；否则输出一行No。
示例1
输入:
2 2 0 0 0 1 3 0 0 1 0 1 0 1 0 0
输出:
No Yes
C++(clang++ 11.0.1) 解法, 执行用时: 112ms, 内存消耗: 1392K, 提交时间: 2023-05-02 22:57:31
#include<bits/stdc++.h>
#define N 5005
using namespace std;
int t,n,a[N][N],c[N];
bool vis[N];
bool match(int x){
for(int i=1;i<=n;i++){
if(a[x][i]&&!vis[i]){
vis[i]=1;
if(!c[i]||match(c[i])){
c[i]=x;
return 1;
}
}
}
return 0;
}
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
int num=0;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(match(i)) num++;
}
if(num==n) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}