看是1点看的,实在想不到办法了,求助一下,这个代码的问题在哪,感激不尽。
#include<bits/stdc++.h>
using namespace std;
struct eee{
int to;
int next;
}edge[50000];
int cnt,n,root[501],check[500],match[500];
void add(int x,int y){
//printf("%d %d\n",x,y);
edge[++cnt].to=y;
edge[cnt].next=root[x];
root[x]=cnt;
}
int dfs(int u){
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to;
if(!check[v]){
check[v]=true;
if(!match[v]||dfs(match[v])){
match[u]=v;
match[v]=u;
//printf("check\n");
return true;
}
}
}
return false;
}
int xyl(){
int ans=0;
for(int i=1;i<=n;i++){
if(!match[i]){
memset(check,0,sizeof(check));
if(dfs(i))ans++;
}
// for(int i=1;i<=2*n;i++){
// ; printf("%d ",match[i]);
// }
//putchar(10);
}
return ans;
}
void solve(){
cin>>n;
memset(root,0,sizeof(root));
memset(match,0,sizeof(match));
cnt=0;
string s;
getchar();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
if(x==1){
add(i,j+n);
add(j+n,i);
}
}
}
//printf("%d\n",dfs(41));
if(xyl()==n){
printf("Yes\n");
}
else{
printf("No\n");
}
for(int i=1;i<=n*2;i++){
// if(match[i]==0)printf("%d ",i);
; //printf("%d ",match[i]);
}
}
int main(){
freopen("1.in","r",stdin);
int t;
cin>>t;
while(t--)solve();
return 0;
}