注意寻找题面隐藏关系
#include<bits/stdc++.h> using namespace std; const int N=1e5+7; int n,cnt,x,tot,t; int head[N],nxt[N<<1],to[N<<1]; int match[N],flag[N]; int _; void add(int x,int y) { _++; to[_]=y; nxt[_]=head[x]; head[x]=_; return ; } int find(int x)//寻找增广路 { for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(!flag[y]) {//若当前边指的点 仍未匹配 flag[y]=1;//给它匹配上 if(!match[y] ||find(match[y]) ) {//它没有匹配对象 || 它的匹配对象可以改变 match[y]=x;//连上 return 1;//找到了一条增广路 } } } return 0; } void init() { memset(head,0,sizeof(head)); fill(to,to+1+_ ,0); _=0; memset(match,0,sizeof(match)); memset(flag,0,sizeof(flag)); return ; } int main() { ios::sync_with_stdio(false); cin>>t; while(t--) { int x,ans=0; init();//每次注意清空 cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) {//行和列匹配 (边边匹配 cin>>x; if(x)//若为1(黑色 add(i,j); } } for(int i=1;i<=n;i++) { memset(flag,0,sizeof(flag)); if(find(i))//每次寻找时清标记 ans++; } if(ans>=n)//找到的路要是>=n,就可以换出来 cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }